动态规划入门经典问题讲解

最近开始接触动态规划问题，以下浅谈（或回顾）一下这些问题的求解过程。

解题思路

对于动态规划问题，由于最终问题的求解需要以同类子问题作为基础，故需要定义一个dp数组（一维或二维）来记录问题求解的各个状态（避免多次求算重复子问题）；然后就是确认状态转移方程，也就是问题求解的递推公式；由于问题的最终状态需要从最初状态递推而来，故需初始化状态，即初始化dp数组。

步骤如下：

1. 确定dp数组以及下标的含义

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

（上述步骤来自代码随想录）

爬楼梯问题

爬楼梯时每一次只能上1级或2级阶梯，问爬n级阶梯有多少种方法？

这是一个最简单的动态规划问题，以下是解题步骤：

1. 定义数组int dp[1005],根据问题的问法，设dp[n]表示爬n级楼梯时的方法总数;

2. 确认状态转移方程，我们直接考虑最后一次爬上n级楼梯的方法。显然，最后一次无非直接爬1级阶梯上到第n级，或者爬2级阶梯上到了第n级。由于前者是发生在已爬n-1级阶梯的基础上，而后者发生在已爬n-2级阶梯的基础上。故爬n级阶梯的方法总数等于dp[n-1]+dp[n-2],即转台转移方程：dp[n] = dp[n-1]+dp[n-2]；

3. 确定初始状态,显然dp[n]需要从两个子状态推导而来，故问题的边界为，确认dp[1]与dp[2].易知,dp[1]=1,dp[2]=2;

4. 确定遍历顺序,显然需要从dp[1]与dp[2]往后递推。

第一种情况

第二种情况

（图来自小灰漫画)

#include<iostream>
using namespace std;//dp[i]表示爬i级阶梯时所花费的步数
int dp[1005];
int main() {int n;cin >> n;//初始化dp[1] = 1;dp[2] = 2;//递推公式为:dp[i] = dp[i-1]+dp[i-2] (i>=3)for (int i = 3;i <= n;i++) {dp[i] = dp[i - 1] + dp[i - 2];}cout << dp[n] << endl;return 0;
}

求最大子段

问题描述：给定一个数字序列，称由连续元素组成的序列为该数字序列的子段，问子段元素之和的最大值为何？

由于每一个子段必有一个前缀与后缀，最大子段必有一个前缀或者后缀，我们干脆定义dp[i]表示以序列中第i个元素为后缀的最大子段；定义int a[1005]存储数字序列的各个元素，a[i]表示序列中的第i个元素。解题步骤如下：

1. 定义int dp[1005],dp[i]表示以序列中第i个元素为后缀的最大子段；

2. 确认状态转移方程，每一个元素可以单独作为一个子段，因此对于dp[i]而言，其最大子串无非两种情况：第一，若dp[i-1]>0，那么a[i]单独作为子段，其必定小于第i元素与以序列中第i-1个元素为后缀的最大子段拼接所得到得新子段，此时dp[i] = dp[i-1]+a[i];若dp[i-1]<=0,那么a[i]单独作为子段会使dp[i]更大，故dp[i]=a[i]。即转移方程为：dp[i]=max(dp[i-1]+a[i],a[i])；

3. 确认初始状态，显然获取dp[i]需要得知dp[i-1]，即dp[1]=a[1]

4. 确定遍历顺序，显然从左往右扫描即可。

#include<iostream>
using namespace std;
const int maxn = 1005;
int a[maxn];
int dp[maxn];int main() {int n;cin >> n;for (int i = 1;i <= n;i++) {cin >> a[i];}dp[1] = a[1];for (int i = 2;i <= n;i++) {dp[i] = max(dp[i - 1] + a[i], dp[i]);}int max = dp[1];for (int i = 2;i <= n;i++) {if (max < dp[i]) {max = dp[i];}}cout << max << endl;return 0;
}

求最长上升子序列

问题描述：给定一个数字序列，取其中的部分元素（元素无需连续），要求元素按升序排列，问上升子序列的最大长度，也就是该子序列里面元素的最大个数。

依旧定义int dp[1005]，其中dp[i]表示以序列中第i个元素为结尾的最长上升子序列。对于dp[i]最长上升子序列与后面元素有关，若a[i]>a[i-1]那么必定有dp[i]=dp[i-1]+1,可在a[i]后面的元素中，dp[i-1]并不一定就是最大的，依旧需要遍历dp[1]~dp[i-1]中，满足a[j]<a[i]且a[j]最大的那个上升子序列，从而接到a[i]后面，解题思路如下：

1. 定义int dp[1005],dp[i]表示以序列中第i个元素为结尾的最长上升子序列；

2. 确认递推公式,dp[i] = max(dp[i-1],dp[i-2],..........,dp[1])+1；

3. 确认初始化状态，显然每一个元素的都至少可以单独构成一个长度为1的最长上升子序列，从而设置dp[0]=0,a[0]=-inf (inf表示无穷大)，保证序列中每一个元素都至少能大于a[0];

4. 确认遍历顺序，依旧是从左往右扫描。

#include<iostream>
using namespace std;const int maxn = 1005;
int a[maxn];
int dp[maxn];
const int inf = 0xffffff;//求最长子序列，假设dp[i]表示以第i元素为结尾的最长上升子序列int main(){int n;cin >> n;a[0] = -inf;for (int i = 1;i <= n;i++) {cin >> a[i];}int ans = 0;for (int i = 1;i <= n;i++) {for (int j = 0;j < i;j++) {if (a[i] > a[j]) {dp[i] = max(dp[i], dp[j] + 1);}}ans = max(ans, dp[i]);}cout << ans << endl;return 0;
}

求最大公共子串

问题描述：给定两个字符串a,b,求a与b中公共部分的元素个数.例如：a="abfed",b="bfd",那么最大公共子串ps = "bfd",其元素个数为3.

此时假定一个二维数组int dp[1005][1005],那么dp[i][j]表示a前i个字符构成的子串与b前j个字符构成的子串的最大公共子串。那么此时若a[i-1]==b[j-1],说明字符串a的第i个字符与字符串b的第j个字符相等，那么此时dp[i][j]=dp[i-1][j-1]+1;若a[i-1]!=b[j-1],dp[i][j]=max(dp[i-1][j],dp[i][j]),因为父串a与其他串b的最大子串一定大于或等于该父串a的子串与其他串b的最大子串.

解题思路：

1. 定义int dp[1005][1005],dp[i][j]表示a前i个字符构成的子串与b前j个字符构成的子串的最大公共子串

2. 确认递推公式,若a[i-1]==b[j-1],则dp[i][j]=dp[i-1][j-1]+1;否则，dp[i][j]=max(dp[i-1][j],dp[i][j]).

3. 确认初始化状态，只需要初始化dp[0][0]=0即可。

4. 确认遍历顺序，依旧是从左往右，从上往下扫描。

#include<iostream>
#include<string>
#include<cstdio>using namespace std;
int dp[105][105];
int main() {string a, b;cin >> a >> b;int lena = a.length();int lenb = b.length();memset(dp, 0, sizeof(dp));for (int i = 1;i <= lena;i++) {for (int j = 1;j <= lenb;j++) {if (a[i - 1] == b[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else {dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}}}cout << dp[lena][lenb] << endl;return 0;
}

求编辑距离

问题描述：给定一个字符串S与一个模板字符串T，可以对S进行插、替、删三种操作，问S经过上述操作变为T的最少次数，即为最小编辑距离。

依旧设int dp[1005][1005]，其中dp[i][j]表示S的前i个字符与T的前j个字符的最小编辑距离。

解题思路：

1. 定义int dp[1005][1005],dp[i][j]表示S的前i个字符与T的前j个字符的最小编辑距离；

2. 确认递推公式,若a[i-1]==b[j-1],则dp[i][j]=dp[i-1][j-1];否则，在dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]中，若dp[i-1][j-1]最小说明需要将a[i-1]替换为b[j-1];若dp[i][j-1]最小，需要在S的前i个字符后面添加一个b[j-1];若dp[i-1][j]最小，需要删除a[i-1]。即dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1;

3. 确认初始化状态，需要依次初始化dp[0][0]~dp[0][S.length()]以及dp[T.length()][0];

4. 确认遍历顺序，依旧是从左往右，从上往下扫描。

#include<iostream>
#include<string>
using namespace std;int dp[105][105];//dp[i][j]表示S前i个字符与T前j个字符编辑时的最小距离//求编辑距离
int func(string S,string T) {int lenS;int lenT;lenS = S.length();lenT = T.length();dp[0][0] = 0;for (int i = 1;i <= lenS;i++) {dp[i][0] = i;}for (int j = 1;j <= lenT;j++) {dp[0][j] = j;}for (int i = 1;i <= lenS;i++) {for (int j = 1;j <= lenT;j++) {if (S[i - 1] == T[j - 1]) {dp[i][j] = dp[i - 1][j - 1];}else {dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;}}}return dp[lenS][lenT];
}int main() {string S, T;cin >> S >> T;cout << func(S, T) << endl;return 0;
}