动态规划

利用历史记录，避免重复计算

  1. 定义数组元素含义，用来保存历史数组。
  2. 找出元素之间的关系（类似归纳法）
  3. 找出初始值

例子

一维DP

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

  1. 定义$dp[i]$为青蛙跳到地$i$级台阶的总跳法。

  2. 青蛙跳到第$i$个台阶有两种跳法，分别是从$i-1$和$i - 2$阶跳过来，所以有$dp[i]=dp[i-1]+dp[i-2]$

  3. 下标不允许为负，如果$dp[2]=dp[1]+dp[0]$，第0个台阶就为0种跳法，$dp[1]=1$，此时$dp[2]=1$但是如果有两阶应该有两种跳法才对，因此$dp[2]=2$也是初始值。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
int f(int n) {
	if(n <= 2) return n;
	int dp[n+1];
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	for(int i = 3; i <= n; i ++) {
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[n];
}

二维DP-1

一个机器人位于一个 m x n 网格的左上角

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角

问总共有多少条不同的路径？

  1. 定义$dp[i][j]$为机器人走到$(i,j)$这个位置时，一共有$dp[i][j]$种路径

  2. 机器人要达到$dp[i][j]$有两种走法，分别是从$(i, j-1)$和$(i-1,j)$走到$(i,j)$，所有就有$dp[i][j]=dp[i-1][j] + dp[i][j-1]$

  3. 保证数组下标不为负数，所以$i$和$j$不为0，所以将最上面一侧和最左面一侧置1

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int uniquePaths(int m, int n) {
	if(m <= 0 || n <= 0) {
		return 0;
	}

	int dp[m][n];
	for(int i = 0; i < m; i ++) {
		dp[i][0] = 1;
	}
	for(int i = 0; i < n; i ++) {
		dp[0][i] = 1;
	}

	for(int i = 1; i < m; i ++) {
		for(int j = 1; j < n; j ++) {
			dp[i][j] = dp[i-1][j] + dp[i][j-1];
		}
	}
	return dp[m-1][n-1];
}

二维DP-2

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

1
2
3
4
5
6
7
8
9
举例：
输入:
arr = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

  1. 从左上角走到$(i, j)$这个位置时，最小的路径和是$dp[i][j]$

  2. 要达到$dp[i][j]$有两种走法，分别是从$(i, j-1)$和$(i-1,j)$走到$(i,j)$，但是需要找最小路径和，所有就有$dp[i][j]=min(dp[i-1][j] , dp[i][j-1]) + arr[i][j]$

  3. 保证数组下标不为负数，所以$i$和$j$不为0，所以将最上面一侧和最左面一侧先计算出来

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int minimumPathSum(vector<vector<int>> arr) {
	if(arr.size() <= 0 || arr[0].size() <=0) {
		return 0;
	}
	int m = arr.size();
	int n = arr[0].size();

	int dp[m][n];
	dp[0][0] = arr[0][0];
	for(int i = 1; i < m; i ++) {
		dp[i][0] = arr[i][0] + dp[i-1][0];
	}
	for(int i = 1; i < n; i ++) {
		dp[0][i] = arr[0][i] + dp[0][i-1];
	}
	for(int i = 1; i < m; i ++) {
		for(int j = 1; j < n; j ++) {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
		}
	}
	return dp[m-1][n-1];
}

编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

1
2
3
4
5
6
7
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为$dp[i][j]$

  1. 如果$word1[i]$与$word2[j]$相等，这个时候不需要进行任何操作，显然有$dp[i] [j] = dp[i-1] [j-1]$。

  2. 如果$word1[i]$与$word2[j]$不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下：

  • 如果把字符$word1[i]$替换成与 word2[j] 相等，则有$dp[i][j] = dp[i-1][j-1] + 1$;

  • 如果在字符串$word1$末尾插入一个与 word2[j] 相等的字符，则有 $dp[i][j] = dp[i][j-1] + 1$;

  • 如果把字符$word1[i]$删除，则有$dp[i][j] = dp[i-1][j] + 1$;

那么我们应该选择一种操作，使得$dp[i][j]$的值最小，显然有

$$dp[i][j] = min(dp[i-1][j-1]，dp[i][j-1]，dp[[i-1][j]]) + 1$$

先计算出所有的$dp[0][0….n]$和所有的$dp[0….m][0]$，当有一个字符串的长度为 0 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int minDistance(string word1, string word2) {
	int n1 = word1.length();
	int n2 = word2.length();

	int dp[n1+1][n2+1];
	dp[0][0] = 0;
	for(int i = 1; i <= n1; i ++) {
		dp[i][0] = dp[i-1][0] + 1;
	}
	for(int i = 1; i <= n2; i ++) {
		dp[0][i] = dp[0][i-1] + 1;
	}

	for(int i = 1; i <= n1; i ++) {
		for(int j = 1; j <= n2; j ++) {
			// 字符下标少1
			if(word1[i-1] == word2[j-1]) {
				dp[i][j] = dp[i-1][j-1];
			} else {
				dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
			}
		}
	}
	return dp[n1][n2];
}