算法基础05-动态规划

[venaissance]

动态规划

定义

让我们看看维基百科中动态规划的定义，截取其中最关键的一部分

Dynamic programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.

Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

翻译过来就是：动态规划指的是通过把一个问题递归拆解成更加简单的子问题的方式简化一个复杂问题。在计算机科学中，如果一个问题可以通过先拆解成简单子问题，寻递归找到每个子问题的最优解，这样我们就可以认为这个问题存在最优子结构。

本质

分治+最优子结构（每步选最优，淘汰次优）

动态规划“三板斧”

1. 分治，找到最优子结构 opt[n]=best_of(opt[n-1], opt[n-2], ...)

2. 状态定义，i 条件时的状态 f[i]

3. DP方程，也就是递推公式，例如一维的斐波那契递推公式 dp[i] = dp[i-1] + dp[i-2]

   二维递推公式例如 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) ，高级的DP公式可能会达到三维甚至三维以上

经典问题

62.Unique Path

思路：

1. 暴力递归，指数级时间复杂度

2. DP

   a. 分治（子问题） path = path(top) + path(left)

   b. 状态定义 f[i, j] 表示第i行第j列的不同路径数

   c. DP方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < n; i++) dp[0][i] = 1;
        for(int i = 0; i < m; i++) dp[i][0] = 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公式dp[i][j] = dp[i-1][j] + dp[i][j-1]，我们还可以继续优化，因为求的是到达终点的不同路径，我们没必要保存到每行每列任意点的不同路径数，其实只需要保存每一行任意点的路径数即可，DP方程可以更新为 dp[i] = dp[i] + dp[i-1]

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[m];
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j > 0) dp[j] += dp[j-1];
            }
        }
        return dp[m-1];
    }
}

1143.最长公共子序列LCS

思路：

1. 暴力

2. DP

   a. 分治 LCS[i] = max（LCS(最后一个字母相同)，LCS(最后一个字母不相同)）

   b. 状态定义 f[i][j] 第一个字符串索引 0-i 构成的子串与第二个字符串索引 0-j 子串的最长公共序列

   c. DP方程

if text1[-1] == text2[-1]:
        dp[i][j] = dp[i-1][j-1] + 1
    else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Java 实现

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int[][] dp = new int[s1.length+1][s2.length+1];
        for (int i = 1; i < s1.length+1; ++i) {
            for (int j = 1; j < s2.length+1; ++j) {
                if(s1[i-1] == s2[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[s1.length][s2.length];
    }
}