动态规划相关题目

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。动态规划是按照时间或者空间特征，将复杂问题划分为小问题：

状态：问题在不同阶段所处情况，一般问题问什么状态设为什么

状态转移方程：根据上一阶段的状态和决策推导出本阶段的状态

边界条件：递推的起始状态，要看一下转移方程，看第一个满足转移方程的起始状态需要的计算初始条件，一般就是dp[0]和dp[1]的初始值。

遍历方向：整个求解过程可以用一个最优决策表来描述，行表示决策的阶段，列表示问题状态。每一格填写的解对应于此问题在某个子状态下的最优解。问题求解时从左上角或右上角开始，以行优先或列优先的顺序，遍历整个表格。

1.基础题目  

509. 斐波那契数 - 力扣（LeetCode）

状态：f(n)是多少

转移方程：dp[n]=dp[n-1]+dp[n-2]

边界条件： 由于第一个满足转移方程的起始状态是dp[2]，因此需要先设定dp[0]和dp[1]

遍历方向：从前到后

从转移方程可以看出，每一个状态只与它的前两步状态有关，因此可以使用滚动数组法来减小空间复杂度。令p,q=dp[i-2],dp[i-1]，dp[i]=p+q，再将dp[i]赋值给q，q的值赋给p,迭代更新

相似题目练习： 

 70. 爬楼梯 - 力扣（LeetCode）

跳台阶扩展问题_牛客题霸_牛客网

343. 整数拆分 - 力扣（LeetCode）

状态：分拆数字i，可以得到的最大乘积为dp[i]

转移公式：dp[i]=j*(i-j)或dp[i]=j*dp[i-j]中的较大者

注意两层循环，单层数组，转移公式中一定还有它自己

dp[i]=max(dp[i],j*(i-j),j*dp[i-j])

边界条件：dp[2]=1,因为0和1没办法拆分，也就没有意义。n也要包含进去，因此外层循环终止为n+1，由于0和1没有记入我们的动态数组，因此内层j最大为i-2，内层循环范围为[1,i-2]

遍历顺序：从前往后，从小到大

因为有多种拆分方案，所以两层循环，内层遍历所有可能的i和i-j的组合，同时dp[i]始终维护的为最大值。

96. 不同的二叉搜索树 - 力扣（LeetCode）

状态：i个节点组成的不同二叉搜索树有dp[i]个

转移公式：dp[i]+=dp[以j为头结点的左子树节点数量]*dp[以j为头节点的右子树节点数量]

边界条件：从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。

从递归公式上来讲，dp[以j为头结点的左子树数量] * dp[以j为头结点的右子树数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。所以初始化dp[0] = 1

遍历顺序：从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。那么遍历i里面每一个数作为头结点的状态，用j来遍历，两层循环。其中外层要包括n，故为2到n+1，内层最小为1，因此为1到i+1(i+1即只有左子树，或全部节点组成只有右子树)

32. 最长有效括号 - 力扣（LeetCode）

状态：包含当前s[i]个括号在内的子括号串中最长的有效括号长度

转移公式：

1）如果s[i]=='('，包含s[i]在内的子串肯定不是有效括号，所以dp[i]=0

2）如果s[i]==')'，如果s[i-1]是'（‘，则dp[i]=dp[i-2]+2；如果s[i-1]也是')'，则去找之前的是不是有没配对的'('，这种需要满足单独的左括号索引i-dp[i-1]-1>=0，并且是s[i-1-dp[i-1]]=='('，dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2 

遍历方向：从1开始遍历

22. 括号生成 - 力扣（LeetCode）

状态：dp[i]表示生成i对括号的可能性组合

转移公式：生成i对括号其实就是‘（p对括号）’+i-1-p对括号的组合，即dp[i]=‘(dp[p])’+dp[i-1-p]

初始化：total=[None]

遍历顺序：四层循环

2.背包问题

• 01背包

状态：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

转移方程：

• 不放物品i，此时背包最大价值为dp[i,j]=dp[i-1][j]
• 放物品i，此时背包最大价值为dp[i][j]=dp[i-1][j-weight[i]]+value[i]，之所以j也变是因为有容量限制，要放入物品i，就要在之前没放入它的背包最大价值基础上加上i的价值。

初始条件：j为0（即容量为0）,背包的最大价值为0，即dp[i][0]=0；而dp[0][0]=0；dp[0][j]则都等于物品0的价值.。

遍历顺序：从前往后，二维数组，外层物品序号，内层背包容量，从最大容量到j，即刚好能装下该物品的最小容量。最后输出的为动态数组最后一位。意思就是先在每种容量的背包里放物品i，根据容量判断是否能放进去，能放进去背包价值总和就加上value[i]，否则不变；下一次又是试着把i+1放进去。

空间优化，使用一维数组，但注意这种情况下内层的背包容量要从大到小，因为放入物品i时dp[i][j]的最大价值是要在dp[i-1][j-weight[i]]基础上，因此为了防止覆盖，从后往前。或者换言之，背包问题遍历时，都是左上角所有可能性的一个动态累加：

416. 分割等和子集 - 力扣（LeetCode）

将该问题转化为背包问题：

• 背包的体积为sum / 2，如果能找到一部分元素的和为sum/2，则另一部分也一定为sum/2，即实现了等分数组。
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

 状态：dp[j]表示当前是否存在子集的和为j

转移公式：dp[j]=dp[j]|dp[j-nums[i]]

初始化：dp=[False]*total

遍历顺序：外层从小到大，内层倒序，从target-num到num

行：表示nums中的元素，列：表示背包容量，即元素总和。每一个小方格有两个选择，放入行号代表的物品，价值就是之前的基础上（该方格左上角的）加上该物品的；不放入该物品，价值就和上一行的该位置一样。

494. 目标和 - 力扣（LeetCode）

通过转化，要使得数组内部元素或加或减以后得到target，假设加起来的元素和为x，减去的元素和则为sum(target)-x，则应该有x-(sum-x)=target，转化可得x=(sum+target)/2。问题变成了用数组装满容量为x的背包有几种方法，和上一题一样了，不过上一题是判断是否可以，这一题要算有几种分法，因此数组初始化条件要改变。

状态：dp[j]表示用当前数组找出元素和为j的子集有几个

转移公式：dp[j]+=dp[j]+dp[j-num]（上一题是证明是否存在，这里是要求总共有多少种，因此就需要把可能的都加起来）

初始化：dp=[1]+[0]*x

遍历顺序同上，注意sum+target是奇数或者小于0则返回为0

• 完全背包：

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。01背包内层循环为了防止覆盖是从后往前遍历；而完全背包问题是从小容量到大容量。

完全背包问题内外循环可以先遍历物品也可以先遍历背包，但要注意，如果是外层物品内层容量，则求出的是组合（因为这种不会出现物品重复）；而如果换过来，求出来的实际是排列，会出现元素一样但次序不一样的情况。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

518. 零钱兑换 II - 力扣（LeetCode）

由于每种金额的硬币数量不限，因此这就是一个完全背包问题。

状态：dp[j]表示凑成金额数为j的组合有几个

转移公式：dp[j]+=dp[j-coin]

初始化：dp[0]=1

遍历顺序：由于是求组合数，外层硬币，内层金额总和，且内层从coin到amount

322. 零钱兑换 - 力扣（LeetCode）

相比于上一题，这一题要计算耗费最少的硬币数目。所以转移公式要取dp[j]和dp[j-coin]+1中最小的，之所以要加一是要添加一个金额为coin的硬币则数量多1。

初始化：dp[0]=0，因为凑足金额为0需要的硬币数就是0；考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖，而对于金额来说，最多就是全用金额为1的硬币凑足，因此数量就是amount+1。

注意最后输出要判断一下是不是能凑到这个金额，使用dp[amount]和amount+1比较大小，如果能凑到肯定结果小于amount+1，否则说明凑不到返回-1

279. 完全平方数 - 力扣（LeetCode）

和上一题完全一样，只是硬币换成了完全平方数，完全平方数即i*i<j的所有数作为硬币进行动态迭代，coin变成了num*num

状态：和为j的完全平方数的最少数量为dp[j]

转移方程：dp[j]=min(dp[j],dp[j-i*i]+1)

初始化：和上一题一致，dp[0]=0,dp[j]=j(即最坏的情况就是用1来表示j)

139. 单词拆分 - 力扣（LeetCode）

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

状态：str[j]是否可以被拆分成单词表里的一个或多个单词

转移公式：如果dp[j-i]为true,&&str[i:j]也在单词表里，则dp[j]也为true。

注意，外层循环中j是从1到len(s)+1，按理来说表示s索引时应该减1，但由于在表示时j-word表示的恰好是下一个单词开始位置，而s[j-len(word):j]中j刚好取不到，也就不用-1

初始化：从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]一定要为true，否则递归下去后面都都是false了。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

遍历方向：外层遍历背包，内层遍历单词；因为如果和之前那样，需要先把所有子串都放在容器里，标记他们是否在单词表中，增加了计算空间。

3. 打家劫舍

考虑要素始终如198所示，只是在198的基础上增加了一些约束，只需要稍作变化就可以转化为198的形式进行求解。

198. 打家劫舍 - 力扣（LeetCode）

状态：dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

转移公式：存在两种情况：1）偷，则dp[i]=dp[i-2]+nums[i]；2）不偷，则dp[i]=dp[i-1]，取两个里面最大的

初始化：递推公式的基础就是dp[0] 和 dp[1]，从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

遍历方向：从前往后

213. 打家劫舍 II - 力扣（LeetCode）

各要素和上一题一样，区别只是在于这一题中首尾相接了，因此可以尽行分情况讨论。

1）不考虑首房间，房间数组相当于变成nums[1:]，转化为198的形式

2）不考虑尾房间，房间数组相当于变成nums[:-1]，转化为198

特例就是只有一户，则输出nums[0];有两户，则输出较大的 

337. 打家劫舍 III - 力扣（LeetCode）

变为二叉树的形式，要用后序遍历，每一个节点都要返回两个最大值：

1）偷它，则它的价值加左右子节点中不偷

2）不偷它，左右子节点中偷或不偷中较大的和

4. 买卖股票

最终输出的肯定是手里不含股票的状态下的最大值

121. 买卖股票的最佳时机 - 力扣（LeetCode）

状态：dp[i][0]表示第i天持有股票所得最多现金，dp[i][1]表示第i天不持有股票所得最多现金；

转移公式：

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
• 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]。注意的是，这题股票只能买卖一次，因此在买入股票前，手上的资金始终为0.

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], dp[i][1]-prices[i]);

如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
• 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

 初始化：dp[0][0]=-prices[0]，dp[0][1]=0

遍历顺序：从前往后

空间优化：由于这道题状态改变只和前一天有关，因此也可以用滚动数组来减小空间

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

这题和上一题最大区别在于可以多次买卖股票，但在手里的股票始终只能有一支，因此在买入股票前dp[i][0]=dp[i-1][1]-prices[i]，即买入i股票前，i-1必须处于无股票状态，但它会有积累的现金dp[i-1][1]。其余要素和121都一样

本题也可以用贪心算法，实际上就是将前后差为正的利润全都累加起来。

123. 买卖股票的最佳时机 III - 力扣（LeetCode）​​​​​​

状态：一天一共就有五个状态，

1. 没有操作
2. 第一次买入
3. 第一次卖出
4. 第二次买入
5. 第二次卖出

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

 转移公式：

1）达到dp[i][1]状态，有两个具体操作：

• 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

注意的是，dp[i][1]并不是一定要在i天买入股票，它之前时刻第一次买入，它也可以继承这个状态

2）达到dp[i][2]也有两种情况：

• 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

3）达到dp[i][3]:

• 操作一： 第i天买入股票了，那么dp[i][3] = dp[i-1][2] - prices[i]
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][3] = dp[i - 1][3]

4）达到dp[i][4]：

• 操作一：第i天卖出股票了，那么dp[i][4] = dp[i - 1][3] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][4] = dp[i - 1][4]

初始化：第0天没有操作，就是0，即：dp[0][0] = 0；第0天做第一次买入的操作，dp[0][1] = -prices[0];第0天第一次卖出，由于之前也没有股票，那肯定为0；第二次买入，还是-prices[i]；第二次卖出，dp[0][4]=0

遍历顺序：从前到后

优化空间：采用滚动数组，维护4个变量即可。

• b1：第一次买入，要不沿用上一次的第一次买入状态（b1），要不就是自己买（这里有点类似121，第一次购买，手里没有现金，所以为-prices[i]）
• s1：第一次卖出，沿用上一次(s1)，或者在上一次为第一次买入的状态下卖出(b1+prices[i])
• b2：第二次买入，沿用上一次(b2)，或者在上一次为第一次卖出的情况下买入(s1-prices[i])
• s2：第二次卖出，沿用上一次(s2)，或者在上一时刻第二次买入的基础上卖出(b2+prices[i])

最后输出的就是手里没有股票的状态，即max(s1,s2) 

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

上一题的进阶版，将2变成了k，其实通过上一题可以发现，奇数次状态就是买入，偶数次就是卖出；而每一次买入要不就是继承上一时刻状态，要不就是上一时刻相邻卖出dp[j-1]-prices[i]；而每一次卖出，要不继承，要不就是上一时刻相邻的买入dp[j-1]+prices[i]。

初始化时也是，dp[0][i]中i为奇数的为0，为偶数的为-prices[0]

每一次更新只和相邻天有关，因此只用了一维数组更新即可，最后输出的为dp[-1]，不论买入卖出多少次，最后手里肯定是没有股票才行。

为了表示统一表示，这里多加了一个dp[0]=0，这样第一次买入不需要单独写出来，也可以表示为dp[j-1]-prices[i]，即-prices[0]

309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）

状态：  dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。

• dp[i][0]：手上持有股票的最大收益
• dp[i][1]：手上不持有股票且处于冷冻期的最大收益
• dp[i][2]：手上不持有股票且不处于冷冻期的最大收益

转移公式：

dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i])

dp[i][1]=dp[i-1][0]+prices[i]，注意冷冻期只能持续一天，不能继承，下一次冷冻期只能变为不持有股票且不处于冷冻期

dp[i][2]=max(dp[i-1][2],dp[i-1][1])

初始化：dp[0][0]=-prices[i]

               dp[0][1]=0

               dp[0][2]=0

遍历顺序：从前到后 

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

只是在122的基础上多加了卖出股票的手续费， 即转移公式dp[i][1]=dp[i-1][0]+prices[i]-fee

最后

以上就是愤怒红酒为你收集整理的动态规划相关题目的全部内容，希望文章能够帮你解决动态规划相关题目所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。