什么是动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

在关于贪心算法，你该了解这些！中举了一个背包问题的例子。

例如：有 N 件物品和一个最多能背重量为 W 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j] 是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。所以贪心解决不了动态规划的问题。

其实大家也不用死扣动规和贪心的理论区别，后面做做题目自然就知道了。
而且很多讲解动态规划的文章都会讲最优子结构啊和重叠子问题啊这些，这些东西都是教科书的上定义，晦涩难懂而且不实用。

大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。
上述提到的背包问题，后序会详细讲解。

动态规划解题步骤

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。
对于动态规划问题，拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

1. 确定 dp 数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？ 因为一些情况是递推公式决定了 dp 数组要如何初始化！

leetcode 刷题导航