Java教程

动态规划学习总结

本文主要是介绍动态规划学习总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

本文结合 代码随想录 + leetcode官方解答,做了学习和总结,仅个人记录学习。

代码随想录网址代码随想录

动态规划大致分为以下几个问题:

1.基础动态规划

2.背包问题

3.打家劫舍

4.股票问题

5.子序列问题

1.基础动态规划

基础使用场景:多为计算最少个数,返回一般为一个整数
解决基本思路:
1考虑前一个状态和该状态的影响关系(递推公式)
2注意起始状态(初始化)
3考虑遍历时需要的基础存储量(如数组,变量),决定了循环的层数

2.背包问题

2.1    01背包问题

2.1.1基础背包问题

问题:背包总承重量、物品重量+物品价值,每个物品最多取1次,求背包装载最大价值。
解法:二维数组,dp[i][j],i表示物品,j表示0-m(m为背包承受的最大重量),dp[i][j]表示j重量下前          i 个物品所能达到的最大价值。
     横向遍历:前i个物品所能装载到该重量下的最大价值。
     赋值:第i个物品在j重量下只有两个状态,要么装要么不装,所以只用对两个值比较选最大
                不装:为dp[i-1][j]的值
                装:为dp[i-1][j-w]的值
                比较后取最大值。
     结果:取dp[i][j]

eg.)

 2.1.1变种背包

问题:从数据集中选出部分数,使这些数总和达到某个值n,数据集中的每个数最多取1次。
解法:二维数组,dp[i][j],i表示数字,j表示0-n(n为到达值),dp[i][j]表示j数值下前i个数是否能

           到达该值,为bool。
           关键不同点为dp[i][j]为bool值,核心为是否能到达这个值。
           判断方式和01背包相同,要么取值,要么不取值。
                      即 取:dp[i-1][j-n[I]]为true,则为true
                           不取:dp[i-1][j]为true,则为true

 优化:

    dp[0] = true
    for _, weight := range stones {
        for j := m; j >= weight; j-- {
            dp[j] = dp[j] || dp[j-weight]
        }
    }

 

 

 

这篇关于动态规划学习总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!