各种各样的动态规划小结
coconutnut
 2020-03-14 18:44:11      

填充dp数组的方式

目前碰到的题目中，一般填充dp要么是按照顺序一个一个填，要么是先全初始化为-1，缺哪个补哪个

以最长上升子序列为例

按顺序扫描

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
26
class Solution {
    
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0){
            return 0;
        }

        int[] dp = new int[nums.length];

        int max = 0;
        for(int i=0;i<nums.length;i++){
            dp[i] = 1;
            if(i>0){
                for(int k=0;k<i;k++){
                    if(nums[i]>nums[k]){
                        dp[i] = Math.max(dp[i],dp[k]+1);
                    }
                }
            }
            max = Math.max(max,dp[i]);
        }

        return max;
    }

}

按需要计算

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
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    private Integer[] dp;
    private int[] nums;

    public int lengthOfLIS(int[] nums) {
        if(nums.length==0){
            return 0;
        }

        this.nums = nums;
        dp = new Integer[nums.length];
        Arrays.fill(dp,-1);

        int max = 0;
        for(int i=0;i<nums.length;i++){
            max = Math.max(max,getDp(i));
        }

        return max;
    }

    public int getDp(int i){
        if(dp[i]==-1){
            dp[i] = 1;
            if(i>0){
                for(int k=0;k<i;k++){
                    if(nums[i]>nums[k]){
                        dp[i] = Math.max(dp[i],getDp(k)+1);
                    }
                }
            }
        }

        return dp[i];
    }
}

一些想法

在这个例子中，由于dp的每个元素都需要填充（然后找最大值），而且可以方便的按照顺序遍历，所以方法一显得简单一些

但是有的题目中顺序不是很好找，比如有的二维dp数组中，要填充的是三角形区域，有的是从左往右扫，有的是从上往下扫，其它一些奇怪的dp几乎找不到顺序

而且很多题目中并不需要把整个dp都填满，只需要得到特定一个元素即为答案，其实没必要按顺序把所有的元素都算出来

1
2
3
4
5
6
7
8
9
10
// getDp真是非常套路
public int getDp(int i){
  if(dp[i]==-1){
    // 没算过就算
    // 算的过程中继续getDp(k)
  }
  
  // 算过了直接返回
  return dp[i];
}

所以感觉，很容易找到顺序、或者必须填满的可以用方法一，其它的直接getDp()省脑细胞

一维

例1 最长上升子序列 (LeetCode 300)

link

描述

给定一个无序的整数数组，找到其中最长上升子序列的长度

状态表示

1
dp[i] 表示第i个元素（包含i）之前最大上升子序列的长度

状态转移方程

1
2
dp[i] = max{ dp[k] + 1}
其中 0<=k<i 且 nums[i]>nums[k]

实现

见：填充dp数组的方式

二维

例1 最长公共子序列问题（算法设计技巧与分析 沙特版 p130）

描述

找两个字符串的最长公共子序列长度

如A=zxyxyz B=xyyzx 则最长公共子序列为xyyz

状态表示

1
2
令 A = a1a2…an，B = b1b2…bn
L[i , j] 表示 a1a2…ai 和 b1b2…bj 的最长公共子序列的长度

状态转移方程

1
2
当 A[i] == B[i]，L[i , j] = L[i-1 , j-1] + 1
当 A[i] != B[i]，L[i , j] = max{ L[i-1 , j] , L[i , j-1] }

eg:
A = horse，B = ros
i为2，j为2时，o == o，L[ ho , ro ] = L[ h , r ] + 1
i为3，j为3时，r != s，L[ hor , ros ] = max{ L[ ho , ros ] , L[ hor , ro ] }

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int LCS(String word1, String word2) {
	
  int[][] dp = new int[word1.length()+1][word2.length()+1];
    
	for(int i=1;i<word1.length()+1;i++) {
		for(int j=1;j<word2.length()+1;j++) {
			if(word1.charAt(i-1)==word2.charAt(j-1)) {
				dp[i][j] = dp[i-1][j-1] + 1;
			}else {
				dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
  
	return dp[word1.length()][word2.length()];
}

例2 编辑距离 (LeetCode 72)

link

描述

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

操作包括：

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

状态表示

1
2
令 A = a1a2…an，B = b1b2…bn
L[i , j] 表示 a1a2…ai 和 b1b2…bj 的最短编辑距离

和公共子序列一样

状态转移方程

1
2
3
当 A[i] == B[i]，L[i , j] = L[i-1 , j-1]
当 A[i] != B[i]，L[i , j] = min{ L[i-1 , j-1] , L[i-1 , j] , L[i , j-1] } + 1
其中，L[i-1 , j-1]代表替换操作，L[i-1 , j]代表删除操作，L[i , j-1]代表插入操作

eg:
A = horse，B = ros
i为2，j为2时，o == o，L[ ho , ro ] = L[ h , r ]，无需继续编辑
i为3，j为3时，r != s，L[ hor , ros ] = min{ L[ ho , ro ] , L[ ho , ros ] , L[ hor , ro ] } + 1
L[ ho , ro ] + 1 代表，在ho已经编辑成ro之后，将r替换成s
L[ ho , ros ] + 1 代表，在ho已经编辑成ros之后，将r删除
L[ hor , ro ] + 1 代表，在hor已经编辑成ro之后，插入s

实现

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
26
27
class Solution {
    public static int minDistance(String word1, String word2) {
	
        int[][] dp = new int[word1.length()+1][word2.length()+1];
    
        for(int i=1;i<word1.length()+1;i++) {
    	    dp[i][0] = i;
        }
        for(int i=1;i<word2.length()+1;i++) {
    	    dp[0][i] = i;
        }
    
    	for(int i=1;i<word1.length()+1;i++) {
	    	for(int j=1;j<word2.length()+1;j++) {
		    	if(word1.charAt(i-1)==word2.charAt(j-1)) {
			    	dp[i][j] = dp[i-1][j-1];
    			}else {
	    			int min = Math.min(dp[i-1][j], dp[i][j-1]);
		    		min = Math.min(min, dp[i-1][j-1]);
			    	dp[i][j] = min+1;
			    }
    		}
	    }	
	
	    return dp[word1.length()][word2.length()];
    }
}

注意

这题dp第0行和第0列初始化为0,1,2,3…

例3 回文子串 (LeetCode 647)

link

描述

统计给定字符串中回文子串的个数

如”aaa”中有”a”, “a”, “a”, “aa”, “aa”, “aaa”共6个

状态表示

1
dp[i][j] 表示字符串的第i到j位(含)是否为回文串

状态转移方程

见注释

实现

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    Integer[][] dp;

    public int countSubstrings(String s) {
        if(s.length()==0){
            return 0;
        }
        
        dp = new Integer[s.length()][s.length()];
        for(int i=0;i<s.length();i++){
            Arrays.fill(dp[i],-1);
        }
        
        int cnt = 0;
        for(int i=0;i<s.length();i++){
            for(int j=i;j<s.length();j++){
                if(getDp(i,j,s)==1){
                    cnt++;
                }
            }
        }

        return cnt;
    }

    public int getDp(int i,int j,String s){
        if(dp[i][j]==-1){
            if(i==j){
                // "a"是
                dp[i][j] = 1;
            }else if(s.charAt(i)!=s.charAt(j)){
                // "ab"、"a***b"不是
                dp[i][j] = 0;
            }else{
                if(j-i==1){
                    // "aa"是
                    dp[i][j] = 1;
                }else{
                    // "a****a"
                    if(getDp(i+1,j-1,s)==1){
                        // 中间是则是
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = 0;
                    }
                }
            }
        }

        return dp[i][j];
    }
}

三维

例1 二指输入的的最小距离 (LeetCode 1320)

link

描述

二指输入法键盘上，每个字母可用坐标表示，如P(2,3)

给定一个待输入字符串，计算仅用两根手指，输入该字符串的最小移动距离（起始位置任意，代价位0）

距离按 |x1-x2| + |y1-y2| 计算

状态表示

1
2
dp[i][l][r] 表示输入完第i个字母后，左手位置为l，右手位置为r
l、r对应字母编号，如A-0,B-1

状态转移方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
记第i个字母位cur，第i-1个字母为pre

1.左手移动到cur处
	- 移动前左手在pre处，则左手必然从pre移到cur，右手可以在任意位置m
	   dp[i][cur][m] = dp[i-1][pre][m] + dis(pre,cur);
	- 移动前右手在pre处(即m==pre)，则左手可以从任意位置n移到cur
	   dp[i][cur][m] = dp[i-1][n][m] + dis(n,cur);

故 dp[i][cur][m] = min{ dp[i-1][pre][m] , dp[i-1][n][pre] }
其中m取值0~26，n取值0~26

2.右手移动到cur处
	- 移动前右手在pre处，则右手必然从pre移到cur，左手可以在任意位置m
	   dp[i][m][cur] = dp[i-1][m][pre] + dis(pre,cur);
	- 移动前左手在pre处(即m==pre)，则右手可以从任意位置n移到cur
	   dp[i][m][cur] = dp[i-1][m][n] + dis(n,cur);

同上，dp[i][cur][m] = min{ dp[i-1][pre][m] , dp[i-1][n][pre] }

实现

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    public int minimumDistance(String word) {

        int[] words = new int[word.length()];
        for(int i=0;i<word.length();i++){
            words[i] = word.charAt(i) - 'A';
        }

        int[][][] dp = new int[words.length][26][26];

        for(int i=0;i<26;i++){
            // 左手开始
            dp[0][words[0]][i] = 0;
            // 右手开始
            dp[0][i][words[0]] = 0;
        }

        for(int i=1;i<words.length;i++){
            int cur = words[i];
            int pre = words[i-1];
            int dis = calDis(cur,pre);
            // 至少有一只手在cur，另一只手可以在任意位置
            for(int m=0;m<26;m++){
                // 右手不动，左手从pre移到cur（上一个字符是左手按的）
                dp[i][cur][m] = dp[i-1][pre][m] + dis;
                // 左手不动，右手从pre移到cur（上一个字符是右手按的）
                dp[i][m][cur] = dp[i-1][m][pre] + dis;
                if(m==pre){
                    // 移动前另一只手刚好在pre处
                    for(int n=0;n<26;n++){
                        int dis2 = calDis(n,cur);
                        // 右手不动，左手从任意位置移到cur（上一个字符是右手按的）
                        dp[i][cur][m] = Math.min(dp[i][cur][m],dp[i-1][n][m]+dis2);
                        // 左手不动，右手从任意位置移到cur（上一个字符是左手按的）
                        dp[i][m][cur] = Math.min(dp[i][m][cur],dp[i-1][m][n]+dis2);
                    }
                }
            }
        }

        int min = Integer.MAX_VALUE;
        int last = words[words.length-1];
        for(int m=0;m<26;m++){
            min = Math.min(min,dp[words.length-1][last][m]);
            min = Math.min(min,dp[words.length-1][m][last]);
        }

        return min;
    }

    public int calDis(int a, int b){
        int x1 = a / 6, y1 = a % 6;
        int x2 = b / 6, y2 = b % 6;
        return (int)(Math.abs(x1 - x2)) + (int)(Math.abs(y1 - y2));
    }
}

优化为二维

由于两只手是完全对称的，不需要知道具体哪只手在cur处，只要有一只在就行了

状态表示

1
dp[i][rest] 表示一只手在cur，另一只手在rest处时的最小移动距离

状态转移方程

1
2
3
4
5
一只手从pre移动到cur，另一只手随便在哪
dp[i][anywhere] = dp[i-1][anywhere] + dis(pre,cur)

若另一只手恰好在pre处，这只手可以从任何地方移动到cur
dp[i][pre] = dp[i-1][anywhere] + dis(anywhere,cur)

实现

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int minimumDistance(String word) {

        int[] words = new int[word.length()];
        for(int i=0;i<word.length();i++){
            words[i] = word.charAt(i) - 'A';
        }

        int[][] dp = new int[words.length][26];
        for(int i=1;i<words.length;i++){
            int cur = words[i];
            int pre = words[i-1];
            int dis = calDis(cur,pre);
            for(int m=0;m<26;m++){
                // 一只手从pre移动到cur，另一只手随便在哪
                dp[i][m] = dp[i-1][m] + dis;
                if(m==pre){
                    // 另一只手恰好在pre处，这只手可以从任何地方移动到cur
                    for(int n=0;n<26;n++){
                        dp[i][m] = Math.min(dp[i][m],dp[i-1][n]+calDis(n,cur));
                    }
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for(int m=0;m<26;m++){
            min = Math.min(min,dp[words.length-1][m]);
        }

        return min;
    }

    public int calDis(int a, int b){
        int x1 = a / 6, y1 = a % 6;
        int x2 = b / 6, y2 = b % 6;
        return (int)(Math.abs(x1 - x2)) + (int)(Math.abs(y1 - y2));
    }
}

优化前 执行用时：19 ms 内存消耗：42.6 MB

优化后 执行用时：7 ms 内存消耗：38.1 MB

也不多的样子…但是思路简单多了

状态压缩

将状态用二进制串表示，二进制串以int形式作为下标

例1 参加考试的最大学生数 (LeetCode 1349)

link

描述

  • 教室里有的座位是坏的
  • 学生可以看到左、右、左上、右上方向的试卷

计算该考场可以容纳的一起参加考试且无法作弊的最大学生人数

状态压缩

用一个二进制串表示一行中每个位置有没有人坐

如 0011 表示 无无有有，记为3

状态表示

1
dp[row][pre] 表示当row-1行的坐法为pre时，第row行及后面所有行最多坐多少人

其中，pre初始化的大小为 1 << 列数

如 有6列，最多 2 ^ 6 种坐法，即 1 << 6

状态转移方程

1
2
dp[row][pre] = max{ dp[row+1][cur] + Integer.bitCount(cur) }
其中cur是row行所有可行状态

每次需先判断坐法为 cur 是否可行

结果

1
dp[0][0] 即为 第-1行没人坐时，第1行及后面所有行最多坐的人数

实现

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
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    private char[][] seats;
    private Integer[][] dp;

    public int maxStudents(char[][] seats) {
        this.seats = seats;
        dp = new Integer[seats.length][1 << seats[0].length];

        int ret = getDp(0,0);
        return ret;
    }

    public int getDp(int row,int pre){
        if(row == seats.length){
            return 0;
        }

        if(dp[row][pre] == null){
            int res = 0;
            // 遍历row行所有坐法
            for(int i=0;i<dp[0].length;i++){
                // 检查是否符合要求
                if(isValid(row,pre,i)){
                    int backNum = getDp(row+1,i);     // 后排能坐多少
                    int curNum = Integer.bitCount(i); // 本排能坐多少
                    res = Math.max(res,backNum+curNum);
                }
            }
            dp[row][pre] = res;
        }

        return dp[row][pre];
    }

  	// 判断当第row-1行坐法为pre时，row行坐法为cur是否可行
    private boolean isValid(int row, int pre, int cur) { //... }

}