网站建设吉金手指专业15,wordpress内容表单,雪域什么网站是做电影的,传奇新开网站目录
1.什么是动态规划?
PS#xff1a;动态规划 VS 贪心
2.动态规划的解题步骤
①确定dp数组#xff08;dp table#xff09;以及下标的含义。
②确定递推公式/状态转移公式。
③dp数组如何初始化。
④确定遍历顺序。
⑤举例推导dp数组。
3.动态规划应该如何debug…目录
1.什么是动态规划?
PS动态规划 VS 贪心
2.动态规划的解题步骤
①确定dp数组dp table以及下标的含义。
②确定递推公式/状态转移公式。
③dp数组如何初始化。
④确定遍历顺序。
⑤举例推导dp数组。
3.动态规划应该如何debug 1.什么是动态规划?
动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的。 PS动态规划 VS 贪心 动态规划中每一个状态是由前一个状态推导出来的。贪心没有状态推导而是从局部直接选最优的。 举一个背包问题的例子 例如有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。动态规划中dp[j]是由dp[j-weight[i]]推导出来的然后取max(dp[j], dp[j - weight[i]] value[i])。但如果是贪心呢每次拿物品选一个最大的或者最小的就完事了和上一个状态没有关系。 所以贪心解决不了动态规划的问题。 2.动态规划的解题步骤
①确定dp数组dp table以及下标的含义。
②确定递推公式/状态转移公式。
③dp数组如何初始化。
④确定遍历顺序。
⑤举例推导dp数组。
为什么要先确定递推公式然后在考虑初始化呢——因为一些情况是递推公式决定了dp数组要如何初始化
3.动态规划应该如何debug
写动规题目代码出问题很正常
做动规的题目写代码之前一定要把状态转移在dp数组上的具体情况模拟一遍心中有数确定最后推出的是想要的结果。然后再写代码如果代码没通过就打印dp数组看看是不是和自己预先推导的哪里不一样。如果打印出来和自己预先模拟推导是一样的那么就是自己的递归公式、初始化或者遍历顺序有问题了。如果和自己预先模拟推导的不一样那么就是代码实现细节有问题。这样才是一个完整的思考过程而不是一旦代码出问题就毫无头绪的东改改西改改最后过不了或者说是稀里糊涂的过了。
这也是推导dp数组的重要性体现。
