动态规划经典例题汇总 (附最全题目链接)
本文总结了王道机试指南中动态规划(Dynamic Progamming)部分的所有例题。一.基本思想与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解中得到原问题的解。与分治法不同的是,分治法会使得有些子问题被重复计算多次。而动态规划的做法是将已解决子问题的答案保存下来,在需要子问题答案的时候便可直接获得,而不需要重复计算,节约效率。二.经典题目...
本文总结了《王道机试指南》中动态规划(Dynamic Programming)部分的所有例题以及分析思路、状态转移方程等。有助于完整复习动态规划全部内容。为避免大量代码和题干导致失去主线,本文只写思路,代码可在题目链接内的讨论区找到。
一.基本思想
与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解中得到原问题的解。
与分治法不同的是,分治法会使得有些子问题被重复计算多次。而动态规划的做法是将已解决子问题的答案保存下来,在需要子问题答案的时候便可直接获得,而不需要重复计算,节约效率。
二.经典题目
1. 递推求解问题
1.1斐波那契数列问题 (n阶楼梯上楼问题)
状态转移方程:dp[n] = dp[n-1] + dp[n-2]
2. 最大连续子序列和
2.1(一维) 最大序列和问题
设置一个数组dp[ ],令dp[i]表示以A[i]作为末尾的连续序列的最大和。
状态转移方程:dp[i] = max{ A[i], dp[i-1] + A[i] }
解释:由于dp[i]是以A[i]作为结尾的连续序列最大和,因此只有两种情况:
- 最大和的连续序列只有一个元素,即A[i]本身。也就是
dp[i] = A[i]
。 - 该最长子序列有多个元素,那么此时的
dp[i] = dp[i-1] + A[i]
。
所以取最大值即可。
2.2(二维) 最大子矩阵问题
对于二维情况,假设原二维矩阵的最大子矩阵所在的行为 i 到 j 。
- 当 i = j 时,则最大子矩阵为第 i 行的最大连续子序列和。(转化为一维)
- 当 i != j 时,现在我们已经知道最大子矩阵的行,把从第 i 行到第 j 行的所有元素相加,得到一个只有一行的一维数组,则该一维数组的连续最大和就是最大子矩阵。(同样转化为一维)
3.最长递增子序列
3.1 拦截导弹
同样设置一个数组dp[ ] ,表以A[i]作为末尾的最长递增子序列的长度。
状态转移方程:dp[i] = max{ 1, dp[j] + 1 }。(当 j < i && A[j] < A[i] 时)
解释:由于dp[i]是以A[i]作为末尾的最长递增子序列的长度,因此只有两种情况:
- A[i]之前的元素都比A[i]大,即dp[i] = 1。
- 存在一些A[ j ]比A[ i ]小,只需找出最大的
dp[j] + 1
存入dp[i]
。
则最长递增子序列的长度即为dp中的最大值。
3.2 最大上升子序列和问题
该题目中,用dp表示的便不是长度了,而是以A[i]作为末尾的最大上升子序列和。其原理与求最长递增子序列的原理完全一致。
状态转移方程:dp[i] = max{ A[i], dp[j] + A[i] }。(当 j < i && A[j] < A[i}时)
。
3.3 合唱队形
这道题有点难,有时间再琢磨。
4.最长公共子序列
4.1 Coincidence(找两个字符串的最长公共子串)
这里要设置一个二维的数组 dp[][]。dp[i][j]
表示以S1[i]作为末尾和以S2[j]作为末尾的最长公共子序列的长度。因此通过设置这样一个数组,最长公共子序列的长度便是数组dp[n][m]
的值。
仔细说来,S1[i]和S2[j]的关系可分为两种情况:
S1[i] == S2[j]
,即两个字符相同。此时必定存在一个最长公共子串以这个字符结尾。其他部分等价于S1中前 i - 1 个字符和S2中前 j - 1 个字符的最长公共子串。则这个子串的长度比dp[i-1][j-1]
多1。即dp[i][j] = dp[i-1][j-1] + 1
。S1[i] != S2[j]
,那此时最长公共子串为S1中的前 i - 1 个字符和S2中的前 j - 1 个字符中最长公共子串长度的较大者。即dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }
。
即
状态转移方程 | 条件 |
---|---|
dp[ i ] [ j ] = dp[ i - 1 ] [ j - 1 ] + 1 | S1[ i ] == S2[ j ] |
dp[ i ] [ j ] = max{ dp[ i - 1 ] [ j ], dp[ i ] [ j - 1 ] } | S1[ i ] != S2[ j ] |
但还要注意一下边界情况,当有一个字符串为空时,公共串长度必为0。即dp[i][0] == dp[0][j] == 0
。
相对于暴力枚举的O(2m+n)复杂度降至了O(mn)。
5.背包问题
5.1 0-1背包 (点菜问题)
该问题描述的是,有n件物品,每件物品的重量为w[i],其价值为v[i],现在有个容量为m的背包,如何选择物品使得装入背包物品的价值最大。
如果暴力枚举所有排列组合,再从中找到最大一组,则时间复杂度为O(2n),下面以O(mn)的时间复杂度解决此问题。
首先设置一个二维数组dp[][],令dp[i][j]表示前 i 个物品装进容量为 j 的背包能获得的最大价值。通过设置这么一个二维数组,数组dp[n][m]值就是0-1背包问题的解。
只考虑第i件物品时,可将情况分为是否放入第i件物品两种:
- 对于容量为j的背包,如果不放入第 i 件物品,那么这个问题就转化为将前 i - 1 个物品放入容量为j的背包的问题,即
dp[i][j] = dp[i-1][j]
。 - 对于容量为j的背包,如果放入第 i 件物品,那么当前背包的容量就变成了 j - w[i] ,并得到了这个物品的价值 v[i]。那么这个问题就转化成了将当前 i - 1 个物品放入容量为 j - w[i] 的背包的问题,即
dp[i][j] = dp[i-1][ j-w[i] ] + v[i]
。
综上,可得状态转移方程:dp[i][j] = max{ dp[i-1][j], dp[i-1][ j-w[i] ] + v[i] }
。
转移时要注意j-w[i]的值是否为非负值,若为负则代表当前容量无法放入第i件物品,不能进行转移。
再考虑一下边界情况:
- 如果装0件物品,不论背包容量多大,能够获得的价值都必为0。
- 如果背包的容量为0,那么无法装入任何物品,能够获得的价值也必定为0。
所以,dp[i][0] = dp[0][j] = 0
。
6.其他问题
6.1 放苹果
链接:https://www.nowcoder.com/questionTerminal/4f0c1e21010e4d849bde5297148e81d9?f=discussion
来源:牛客网
User: 菜鸟葫芦娃
- 设dp(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
- 当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即if(n>m)
dp(m,n) = dp(m,m)
- 当n <= m:不同的放法可以分成两类:
- 有至少一个盘子空着,即相当于
dp(m,n) = dp(m,n-1)
。 - 所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即
dp(m,n) = dp(m-n,n)
。
而总的放苹果的放法数目等于两者的和,即dp(m,n) = dp(m,n-1) + dp(m-n,n)
。
- 有至少一个盘子空着,即相当于
#include <stdio.h>
int dp(int m, int n)
{
if(n==1) return 1;
else if(m==0) return 1;
else if(n>m) return dp(m, m);
else return dp(m, n-1)+dp(m-n, n);
}
int main()
{
int m, n;
while(scanf("%d %d", &m, &n)!=EOF)
{
printf("%d\n", dp(m, n));
}
return 0;
}
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)