1-动态规划算法理论基础

目录

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数组的重要性体现。