算法：动态规划

Weekly Post

四月的第三周，来学习动态规划。

本来上篇博文的题目叫做《回溯与动态规划》，结果我高估了自己的算法能力，根本学不透hhh，这周来学习动态规划，努力把都所有变种都学会并熟练使用。

动态规划（Dynamic programming，简称DP），是一种拆分问题变成相对简单的子问题的算法。我一直觉得这种算法跟高中的数学归纳法有相似之处：在思考问题时，都是思考怎么从第 N 步推出第 N+1 步，在写答案时，都是先写出第 1 步，然后写第 N 步到第 N +1 步的过程，最终输出结论。这种从第 N 步推到第 N+1 步的过程，在算法中称为“重叠子问题”，就是怎么把问题转换成子问题，通常重叠子问题就是解答的核心问题。

动态规划的核心在于写出递推公式，也就是怎么从第 n 步推到第 n+1 步（这个公式的术语叫做状态转移方程），只要能写出这个递推公式，一般问题就不大了。而写出这个公式的通常做法在于画格子，自己画一个表格，每一行新增一个物品/一天/一个数字，自行观察总结新增了一个之后，怎么从上一行信息得出本行信息。

我觉得自己上篇整理算法的方式是错误的，熟练运用算法最重要的不是理解模板，而是大量的练习。本文不再讲解具体内容了，只简单整理 10 道动态规划的题目（题目描述也不抄了，点击题目能跳转过去），画出表格，写出递推公式。

LeetCode53 最大子序和

物品[-2, 1, -3, 4, -1, 2, 1, -5, 4] 背包容量1 1
-2 -2
-2, 1 1
-2, 1, -3 -2
-2, 1, -3, 4 4
-2, 1, -3, 4, -1 3
-2, 1, -3, 4, -1, 2 5
-2, 1, -3, 4, -1, 2, 1 6
-2, 1, -3, 4, -1, 2, 1, -5 1
-2, 1, -3, 4, -1, 2, 1, -5, 4 5 
1
2
dp(i,1) = max( dp(i-1,1) + nums[i], nums[i] )
               在原本基础上新增数字    新增数字本身
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int maxSubArray(int[] nums) {
    // 物品个数：nums.length
    int len = nums.length;
    if (len == 0) {
        return 0;
    }

    // 创建dp数组
    int[] dp = new int[len];

    // 记录结果
    int max = nums[0];

    // 遍历数组，dp[i] = (dp[i-1] + num) || (num)
    for (int i = 0; i < len; i++) {
        if (i > 0) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        } else {
            dp[i] = nums[i];
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

LeetCode416 分割等和子集

物品[1, 2, 3, 4] 背包容量5 0 1 2 3 4 5
1 √
1, 2 √ √ √
1, 2, 3 √ √ √ √ √
1, 2, 3, 4 √ √ √ √ √ 
1
2
dp(i,j) = (j == nums[i]) || (dp(i-1,j)) || (dp[i - 1][j - nums[i]])
          刚好是新加的数字     原本就可以       新加数字之后可以
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
public boolean canPartition(int[] nums) {
    // 校验数据
    int len = nums.length, sum = 0;
    if (len == 0) {
        return false;
    }
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }

    // 物品个数：nums.length
    // 背包容量：总和/2
    int itemCount = len;
    int capacity = sum / 2;
    boolean[][] dp = new boolean[itemCount][capacity + 1];

    // 遍历
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < capacity + 1; j++) {
            // 自己本身
            if (nums[i] == j) {
                dp[i][j] = true;
            }
            // 拷贝上一行
            else if (i > 0 && dp[i - 1][j]) {
                dp[i][j] = true;
            }
            // 自己本身组合上一行
            else if (i > 0 && j > nums[i] && dp[i - 1][j - nums[i]]) {
                dp[i][j] = true;
            }
        }
    }

    return dp[itemCount - 1][capacity];
}

Mi27 石头收藏家

物品[2, 3, 5, 7] 物品价值[1, 5, 2, 4] 背包容量10 0 1 2 3 4 5 6 7 8 9 10
2 1
2,3 1 5 6
2,3,5 1 5 6 3 7 8
2,3,5,7 1 5 6 4 7 5 9 
1
2
dp(i,j) = max( value[i],       dp(i-1,j-nums[j])+value[i], dp(i-1,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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String line, line1 = null, line2 = null, line3;
    while (scan.hasNextLine()) {
        line = scan.nextLine().trim();
        
        if (line1 == null) {
            line1 = line;
        } else if (line2 == null) {
            line2 = line;
        } else {
            line3 = line;

            // 读取数据
            String[] s1 = line2.split(" ");
            String[] s2 = line3.split(" ");
            int capacity = Integer.parseInt(line1);
            int[] weights = new int[s1.length];
            int[] values = new int[s2.length];
            for (int i = 0; i < s1.length; i++) {
                weights[i] = Integer.parseInt(s1[i]);
                values[i] = Integer.parseInt(s2[i]);
            }

            // 动态规划数组 行：物品数量 列：背包容量
            int[][] dp = new int[weights.length][capacity + 1];
            List<Integer> history = new ArrayList<>();
            int max = 0;

            // 初始化
            if (weights[0] <= capacity) {
                dp[0][weights[0]] = values[0];
                history.add(weights[0]);
                max = values[0];
            }

            // 遍历
            for (int i = 1; i < weights.length; i++) {
                // 先拷贝上一行数据
                System.arraycopy(dp[i - 1], 0, dp[i], 0, dp[0].length);
                // 结合之前的数据
                int newWeight = weights[i];
                int newValue = values[i];
                int historyNum = history.size();
                for (int j = 0; j < historyNum; j++) {
                    int hWeight = history.get(j);
                    int hValue = dp[i - 1][hWeight];
                    int nowHeight = hWeight + newWeight;
                    if (nowHeight <= capacity) {
                        dp[i][nowHeight] = Math.max(dp[i - 1][nowHeight], hValue + newValue);
                        max = Math.max(max, dp[i][nowHeight]);
                        if (!history.contains(nowHeight)) {
                            history.add(nowHeight);
                        }
                    }
                }
                // 把本身的数据赋值
                if (newWeight <= capacity) {
                    dp[i][newWeight] = Math.max(dp[i][newWeight], newValue);
                    max = Math.max(max, dp[i][newWeight]);
                    history.add(newWeight);
                }
            }
            printArray(dp);

            line1 = null;
            line2 = null;
            line3 = null;
            System.out.println(max);
        }
    }
}

LeetCode188 买卖股票的最佳时机 IV

（这个解法效率比较差，但是能做出来）

物品[3, 2, 6, 5, 0, 3] 背包容量6 0 1 2 3 4 5 6
3
3, 2
3, 2, 6 4 4 4 4 4 4
3, 2, 6, 5 4 4 4 4 4 4
3, 2, 6, 5, 0 4 4 4 4 4 4
3, 2, 6, 5, 0, 3 4 7 7 7 7 7 
1
2
dp(i,j) = max( (遍历取最大){dp(i-1,j-1)+nums[i]-nums[k]},       dp(i-1,j) )
               第k-1天进行j-1次交易 + （第i天的股票 - 第k天的股票）  不交易，沿用上一天
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
public int maxProfit(int k, int[] prices) {
    if (prices == null || prices.length < 1) {
        return 0;
    }

    int days = prices.length;
    int saleTimes = Math.min(prices.length, k);
    int[][] dp = new int[days + 1][saleTimes + 1];

    // 第i天进行j次交易 = （遍历取最大）{第k-1天进行j-1次交易 + （第i天的股票 - 第k天的股票）}
    for (int i = 0; i <= days; i++) {
        for (int j = 0; j <= saleTimes; j++) {
            // 第1天交易，肯定赚不到钱
            if (i <= 1) {
                dp[i][j] = 0;
            }
            // 交易次数是0，肯定赚不到钱
            else if (j == 0) {
                dp[i][j] = 0;
            } else {
                int max = dp[i - 1][j];
                for (int m = 1; m < i; m++) {
                    max = Math.max(max, dp[m - 1][j - 1] + (Math.max(prices[i - 1] - prices[m - 1], 0)));
                }
                dp[i][j] = max;
            }
        }
    }

    return dp[days][saleTimes];
}

LeetCode32 最长有效括号

物品[(, (, ), (, ), ), (, )] 背包容量1 1
( 0
(( 0
(() 1
(()( 1
(()() 2
(()()) 3
(()())( 3
(()())() 4 
1
2
dp(i)  =  dp(i-2) + 2   ||   dp(i-1) + 2 + dp(i-dp(i-1)-2)
          "()"结尾            "))"结尾 （dp(i-dp(i-1)-2)代表对应的"("之前有多少个有效括号
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
public int longestValidParentheses(String s) {
    // 校验
    if (s == null || s.length() < 2) {
        return 0;
    }

    char[] brackets = s.toCharArray();
    int[] dp = new int[brackets.length];
    int max = 0;

    // 遍历符号
    for (int i = 1; i < brackets.length; i++) {
        if (brackets[i] == ')') {
            int already = 0;
            // ()结尾，则是dp[i-2]+2
            if (brackets[i - 1] == '(') {
                if (i >= 2) {
                    already = dp[i - 2];
                }
                dp[i] = already + 2;
            // ))结尾，则先判断是否成立，如果成立，在上个成立点的基础上+2
            } else {
                if (i - dp[i - 1] - 1 >= 0 && brackets[i - dp[i - 1] - 1] == '(') {
                    if (i - dp[i - 1] - 2 >= 0) {
                        already = dp[i - dp[i - 1] - 2];
                    }
                    dp[i] = dp[i - 1] + 2 + already;
                }
            }
            max = Math.max(max, dp[i]);
        }
    }

    return max;
}

LeetCode44 通配符匹配

物品[*, a, *, b] 背包容量 5 a d c e b
* √ √ √ √ √
*, a √ × × × ×
*, a, * √ √ √ √ √
*, a, *, b × × × × √ 
1
2
dp(i,j) = dp(i-1,j-1) || dp(i-1,j-1) || { dp(i-1,j) || dp(i,j-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
39
40
41
42
43
public boolean isMatch(String s, String p) {
    if (s == null || p == null) {
        return false;
    }

    // 预先过滤一遍"*"，多个连续的*缩减成一个
    String t = "";
    for (char pChar : p.toCharArray()) {
        if (pChar != '*') {
            t += pChar;
        } else if (t.equals("")) {
            t += pChar;
        } else if (t.charAt(t.length() - 1) != '*') {
            t += pChar;
        }
    }

    int m = s.length();
    int n = t.length();

    // 状态 dp[i][j] : 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
    boolean[][] dp = new boolean[m + 1][n + 1];

    // 初始化
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        dp[0][i] = dp[0][i - 1] && t.charAt(i - 1) == '*';
    }

    // 状态转移
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1) || t.charAt(j - 1) == '?') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (t.charAt(j - 1) == '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
        }
    }

    // 返回结果
    return dp[m][n];
}

LeetCode62 不同路径

1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7
3 1 3 6 10 15 21 28 
1
2
dp(i,j) = dp(i-1,j) + dp(i,j-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
public int uniquePaths(int m, int n) {
    if (m == 0 || n == 0) {
        return 0;
    }

    int[][] dp = new int[n][m];
    dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 主要是处理0的特殊情况
            if (i == 0 && j == 0) {
                continue;
            }
            int up = 0, left = 0;
            if (i > 0) {
                up = dp[i - 1][j];
            }
            if (j > 0) {
                left = dp[i][j - 1];
            }
            // 核心逻辑就一行代码，上+左
            dp[i][j] = up + left;
        }
    }

    return dp[n - 1][m - 1];
}

LeetCode72 编辑距离

null r r, o r, o, s
null 0 1 2 3
h 1 1 2 3
h, o 2 2 1 2
h, o, r 3 2 2 2
h, o, r, s 4 3 3 2
h, o, r, s, e 5 4 4 3 
1
2
3
dp(i,j) = n 其中一方是null，采用另一方单词的长度
          || dp(i-1,j-1) 尾字母相同，采用去掉尾字母的dp
          || 1 + min{ dp(i,j-1), dp(i-1,j), dp(i-1,j-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
public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    if (n1 == 0 || n2 == 0) {
        return n1 + n2;
    }

    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 0; i <= n1; i++) {
        for (int j = 0; j <= n2; j++) {
            // 当其中一个单词为null时，dp为另一个单词的长度
            if (i == 0 || j == 0) {
                dp[i][j] = i + j;
            }
            // 当两个单词尾字母相同时，dp(i,j)=dp(i-1,j-1)
            else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            // dp(i,j) = 1 + min{ dp(i,j-1), dp(i-1,j), dp(i-1,j-1) } 代表从任意临近状态过来
            else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
            }
        }
    }

    return dp[n1][n2];
}

LeetCode85 最大矩形

（不好画表格，经过了两次dp，第一次是行，第二次是列）

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
public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }

    int rows = matrix.length, columns = matrix[0].length;
    int result = 0;

    // 行dp一次
    int[][] lineDp = new int[rows][columns];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (matrix[i][j] == '0') {
                lineDp[i][j] = 0;
            } else if (j == 0) {
                lineDp[i][j] = 1;
            } else {
                lineDp[i][j] = lineDp[i][j - 1] + 1;
            }
        }
    }

    int[][] dp = new int[rows][columns];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (i == 0) {
                dp[i][j] = lineDp[i][j];
            } else {
                int columnMin = lineDp[i][j];
                int max = lineDp[i][j];
                for (int k = i - 1; k >= 0; k--) {
                    columnMin = Math.min(columnMin, lineDp[k][j]);
                    if (columnMin == 0) {
                        break;
                    }
                    // 宽：遍历之后的最小值  高：i和k之间的距离
                    int width = columnMin;
                    int high = i - k + 1;
                    max = Math.max(max, high * width);
                }
                dp[i][j] = max;
            }
            result = Math.max(result, dp[i][j]);
        }
    }

    return result;
}

LeetCode279 完全平方数

0
1 1
2 2
3 3
4 1
5 2
6 3
7 4
8 2
9 1
10 2
11 3
12 3 
1
2
dp(i) = i   ||  dp(i)     ||    dp(i-1)+1  ||   平方数   || dp(i-平方数)+1 
        i个1    遍历的上个结果     上个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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public int numSquares(int n) {
    if (n <= 0) {
        return 0;
    }

    // 平方数
    int[] squares = new int[(int) Math.sqrt(n) + 1];
    for (int i = 0; i < squares.length; i++) {
        squares[i] = i * i;
    }

    int[] dp = new int[n + 1];
    for (int i = 1; i < dp.length; i++) {
        // 遍历平方数
        for (int j = 1; j < squares.length && squares[j] <= i; j++) {
            // 如果是平方数，那么dp(i)=1
            if (i == squares[j]) {
                dp[i] = 1;
            }
            // 如果不是平方数，那么dp(i)= { i || 前一个+1 || dp(i-平方数)+1 }
            else {
                if (dp[i] == 0) {
                    dp[i] = min(i, dp[i - 1] + 1, dp[i - squares[j]] + 1);
                } else {
                    dp[i] = min(dp[i], dp[i - 1] + 1, dp[i - squares[j]] + 1);
                }
            }
        }
    }

    return dp[n];
}

private int min(int... nums) {
    int min = nums[0];
    for (int num : nums) {
        min = Math.min(min, num);
    }
    return min;
}