算法【更多二维动态规划题目】

本文不再从递归入手，而是直接从动态规划的定义入手，来解决更多二维动态规划问题。其中包含一些比较巧妙的尝试思路。

题目一

测试链接：https://leetcode.cn/problems/distinct-subsequences/

分析：dp数组的含义是字符串s前i个字符中出现字符串t前j个字符的次数。代码如下。

class Solution {
public:int dp[1001][1001];int MOD = 1000000007;int numDistinct(string s, string t) {int s_length = s.size();int t_length = t.size();dp[0][0] = 1;for(int i = 1;i <= t_length;++i){dp[0][i] = 0;}for(int i = 1;i <= s_length;++i){dp[i][0] = 1;}for(int i = 1;i <= s_length;++i){for(int j = 1;j <= t_length;++j){if(s[i-1] == t[j-1]){dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;}else{dp[i][j] = dp[i-1][j];}}}return dp[s_length][t_length];}
};

从代码中可以看出做空间压缩很容易。代码如下。

class Solution {
public:int dp[1001];int leftup1, leftup2;int MOD = 1000000007;int numDistinct(string s, string t) {int s_length = s.size();int t_length = t.size();for(int i = 1;i <= t_length;++i){dp[i] = 0;}for(int i = 1;i <= s_length;++i){leftup1 = 1;for(int j = 1;j <= t_length;++j){leftup2 = dp[j];if(s[i-1] == t[j-1]){dp[j] = (leftup1 + dp[j]) % MOD;}leftup1 = leftup2;}}return dp[t_length];}
};

其中，辅助变量leftup含义和之前的文章一样。

题目二

测试链接：https://leetcode.cn/problems/edit-distance/

分析：dp数组含义为word1前i字符转换成word2前j个字符所使用的最少操作数。那么就有两种可能，一个是word1的最后一个字符参与变换，一个是word1的最后一个字符不参与变换。对于参与变换来说，一是这最后一个字符变为了word2的最后一个字符，二是最后一个字符变为了word2的倒数第二个字符，这word2的最后一个字符通过插入得到。对于不参与变换来说，次数为word1的前i-1个字符变换为word2的前j个字符的次数加上减去word1最后一个字符。这三种情况取最小值。代码如下。

class Solution {
public:int dp[501][501];int minDistance(string word1, string word2) {int word1_length = word1.size();int word2_length = word2.size();dp[0][0] = 0;for(int i = 1;i <= word2_length;++i){dp[0][i] = i;}for(int i = 1;i <= word1_length;++i){dp[i][0] = i;}for(int i = 1;i <= word1_length;++i){for(int j = 1;j <= word2_length;++j){if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = dp[i-1][j-1]+1;}dp[i][j] = dp[i][j] < dp[i][j-1]+1 ? dp[i][j] : dp[i][j-1]+1;dp[i][j] = dp[i][j] < dp[i-1][j]+1 ? dp[i][j] : dp[i-1][j]+1;}}return dp[word1_length][word2_length];}
};

从代码中可以看出做空间压缩很容易。代码如下。

class Solution {
public:int dp[501];int leftup1, leftup2;int minDistance(string word1, string word2) {int word1_length = word1.size();int word2_length = word2.size();dp[0] = 0;for(int i = 1;i <= word2_length;++i){dp[i] = i;}for(int i = 1;i <= word1_length;++i){leftup1 = i-1;dp[0] = i;for(int j = 1;j <= word2_length;++j){leftup2 = dp[j];if(word1[i-1] == word2[j-1]){dp[j] = leftup1;}else{dp[j] = leftup1+1;}dp[j] = dp[j] < dp[j-1]+1 ? dp[j] : dp[j-1]+1;dp[j] = dp[j] < leftup2+1 ? dp[j] : leftup2+1;leftup1 = leftup2;}}return dp[word2_length];}
};

题目三

测试链接：https://leetcode.cn/problems/interleaving-string/

分析：dp数组的含义为s1的前i个字符和s2的前j个字符能否交错组成s3的前i+j个字符。代码如下。

class Solution {
public:bool dp[101][101] = {false};bool isInterleave(string s1, string s2, string s3) {int length_s1 = s1.size();int length_s2 = s2.size();int length_s3 = s3.size();if(length_s3 != length_s1 + length_s2){return false;}dp[0][0] = true;for(int i = 1;i <= length_s2;++i){dp[0][i] = dp[0][i-1] && s2[i-1] == s3[i-1];}for(int i = 1;i <= length_s1;++i){dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1];}for(int i = 1;i <= length_s1;++i){for(int j = 1;j <= length_s2;++j){if(s3[i+j-1] == s1[i-1]){dp[i][j] |= dp[i-1][j];}if(s3[i+j-1] == s2[j-1]){dp[i][j] |= dp[i][j-1];}}}return dp[length_s1][length_s2];}
};

下面是做空间压缩的解法。代码如下。

class Solution {
public:bool dp[101] = {false};bool isInterleave(string s1, string s2, string s3) {int length_s1 = s1.size();int length_s2 = s2.size();int length_s3 = s3.size();if(length_s3 != length_s1 + length_s2){return false;}dp[0] = true;for(int i = 1;i <= length_s2;++i){dp[i] = dp[i-1] && s2[i-1] == s3[i-1];}bool temp;for(int i = 1;i <= length_s1;++i){dp[0] = dp[0] && s1[i-1] == s3[i-1];for(int j = 1;j <= length_s2;++j){temp = dp[j];dp[j] = false;if(s3[i+j-1] == s1[i-1]){dp[j] |= temp;}if(s3[i+j-1] == s2[j-1]){dp[j] |= dp[j-1];}}}return dp[length_s2];}
};

题目四

有效涂色问题

给定n、m两个参数

一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选

当涂满n个格子，并且m种颜色都使用了，叫一种有效方法

求一共有多少种有效的涂色方法

1 <= n, m <= 5000

结果比较大请 % 1000000007 之后返回

分析：dp数组的含义是i个格子j种颜色有多少种有效的涂色方法。代码如下。

#include <iostream>
#define MOD 1000000007
using namespace std;
int n, m;
int dp[5001][5001] = {0};
int main(void){scanf("%d%d", &n, &m);for(int i = 0;i <= n && i <= m;++i){dp[i][i] = 1;}for(int i = 1;i <= n;++i){dp[i][0] = 1;dp[i][1] = 1;}for(int i = 1;i <= n;++i){for(int j = 1;j <= m && i >= j;++j){dp[i][j] = (dp[i-1][j] * j + dp[i-1][j-1] * (m - j + 1)) % MOD;}}printf("%d", dp[n][m]);
}