【Leetcode】十八、动态规划：不同路径 + 全1的最大正方形

1、动态规划

只能向下、向右的走，从图中左上角走到右下角，有几条路径
因为只能向下、向右走，所以从起始点走到点（R，C），路径数等于，以起始点到点（R，C）为对角线的矩形里，到点（R，C）左侧点的路径数 + 到点（R，C）上边点的路径数 （动态规划的方程式）

// 动态规划的方程式
[R，C] = [R - 1][C] + [R][C - 1]
1
2

有些类似斐波那契数列了，起始点就是[0][0] （动态规划的初始状态），那递归终止的条件，就是其左侧点或者上边点不存在，此时，到它的路径只有一条，return 1，一直算到点（R，C）（动态规划的终止状态）。以上，动态规划的三要素：

• 动态规划的方程式
• 动态规划的初始状态
• 动态规划的终止状态

从起始状态（0，0），到终止状态（R，C），中间每个格子的值（到达它的路径数），都会算出来，这些中间结果，可存入一个数组，这题可用二维数组存。动态规划可用来干：

• 1）计数：有多少种方式或路径，如上面从左上角到右下角有多少路径
• 2）求最值：从左上角到右下角路径的最大数字和，每个数字不等，代表权重，求最长路径或最小路径
• 3）求存在性：是否存在某个可能，可以从A走到B

动态规划的分类：

• 自底向上：从最小的子问题开始，逐步计算出所有可能的状态，直到解决原问题

• 自顶向下：通过递归地方式，从原问题开始，依次分解为更小的子问题，通常需要记忆化搜索（Memoization）来保存已经计算过的结果，避免重复计算

2、leetcode509：斐波那契数列

不再递归了，根据方程式，步步为营，从F(2)一路计算到F(n)，并把每个中间值存入数组中，最后返回数组的第n个元素即可

public class P509Two {
    public int recursion(int n) {
        //F(0)和F(1)
        if (n < 2) {
            return n == 0 ? 0 : 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;  //F(1)
        // 根据方程式，计算每个值，存入数组，从F(2)一路计算到F(5)
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、leetcode62：不同路径

前面已经分析过了，这儿的方程式为：F(m，n）= F(m - 1，n）+ F(m，n - 1），初始状态为（1，1），终止状态为（m，n）

public class P62 {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
            	// 如果是边缘，x轴或者y轴，则直接赋值1，因为只有一条路可达，其余按方程式赋值
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

红圈里的这些，x轴或者y轴上的，到达他们的路径只有一条，因此直接赋值1，别用方程式去计算，会导致数组下标越界。除了这些点，其余按方程式赋值，最后返回(m-1，n-1）位置的值即可。

两道题，给我的个人感觉是，动态规划，就是从初始状态开始，根据方程式，步步为营，经过一个个中间状态的值，到达终止状态 ，最后，如果你需要存储这些中间状态值，一般用数组存储，因为其访问数据的时间复杂度为O(1）。

4、leetcode121：买卖股票的最佳时机

这题，本质就是求数组后面元素与前面元素的差值的最大值，两层for循环，默认返回为0，遇到最大的值就覆盖，即可：

public class P121 {
    public int maxProfit(int[] prices) {
        if (null == prices || prices.length < 2) {
            return 0;
        }
        int result = 0;
        for (int i = 0; i < prices.length - 1; i++) {
        	// 注意内层循环，最快第二天才能卖出，因此，这里是i+1开始
            for (int j = i + 1; j < prices.length; j++) {
                result = Math.max((prices[j] - prices[i]), result);
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

优化下：遍历数组，更新前 i 天的最低买入成本，同时更新前i天的最高利润（第i天与前面i-1天最低价的差值，然后不停覆盖这个差值，取最大值）

public class P121 {
    public int maxProfit(int[] prices) {
        if (null == prices || prices.length < 2) {
            return 0;
        }
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5、leetcode70：爬楼梯

参考上面62题不同路径的思想：

• 62题：到（m，n)的路径数 = 到（m，n)上方点的路径数 + 到（m，n)左侧点的路径数，因为规定了只能向下、向右移动
• 本题：到n阶的路径数 = 到n - 1阶的路径数 + 到 n - 2阶的路径数，因为一次只能走一个或者两个台阶

切入点：动态规划要经过状态转移，那就该想一下，题中要求的状态，怎么可以由上一步到达

由此，动态规划方程式为：

f(n) = f(n - 1) + f(n - 2)
1

代码实现：

public class P70 {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] resultArr = new int[n + 1];
        resultArr[0] = 1;
        resultArr[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            resultArr[i] = resultArr[i - 1] + resultArr[i - 2];
        }
        return resultArr[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

优化下，不存中间值了，因为万一n很大，很浪费内存，而且题目只要最后的值，不需要中间结果

public class P70 {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        // f(x-1)
        int pre = 1;
        // f(x-2)
        int prePre = 0;
        int result = 1;
        for (int i = 1; i <= n ; i++) {
            result = pre + prePre;
            // 状态转移，往前走一步，f(x-2)变成了新的f(x-1)，f(x-1)变成了f(x)
            prePre = pre;
            pre = result;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6、leetcode279：完全平方数

思路一：暴力解法

根据四平方和定理，这题返回的结果肯定是1、2、3、4里的一个。那我找：n是否能由1个平方数搞出来，不行就看是否能由2个平方数搞出来，最多到4，封顶了就。因为这题求的是最少的数量，别说n = 1 + 1 + 1 + …… + 1。借助以下四条数学规律：

实现：

public class P279 {
    public int numSquares(int n) {
        // 消除4的因子
        while (n % 4 == 0) {
            n = n / 4;
        }
        // %8 == 7，一定是4
        if (n % 8 == 7) {
            return 4;
        }
        // 找a和b两个数，使得n = a^2 + b^2，且a和b这些数必然落在区间 [1，根号n]之间
        for (int a = 0; a * a <= n; a++) {
            int b = (int) Math.sqrt(n - a * a);
            if (a * a + b * b == n) {
                // 找到a,b了，如果a或者b是0，说明a^2 = n或者b^2 = n，返回1，反之，返回2
                return (a > 0 && b > 0) ? 2 : 1;
            }
        }
        // 不是1，也不是2，那就是3
        return 3;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路二：动态规划

用几个数的平方的和表示数字n，这几个平方数一定在[1，根号n] 之间，因为根号n的平方就是n了。从1到根号n的范围，遍历，假设遍历到了数字 j，此时剩下 n - j * j ，n - j * j 的平方数字的数量假设为f(n - j * j )，那f(n)就是这个值 + 1，状态转移方程：

f(n) = f(n - j * j ) + 1
1

当然，这题找最小数量，因此，取的是[1，根号n]，最小的平方数的数量，代码实现：

public class P279 {
     public int numSquares(int n) {
        int[] resultArr = new int[n + 1];
        // 算从1到n，每个数的平方数的数量
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            // j * j <= i，即从1到根号n的范围
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, resultArr[i - j * j]);
            }
            resultArr[i] = minn + 1;
        }
        return resultArr[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

7、leetcode221：最大正方形

用 dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值，那这个dp值，应该取决于其左边、上边、右上方三个点的dp值，如下图：

红色方框所在的点（2，3），其dp值，取决于黄色方框里的三个点的dp值，且是像短板水桶一样，全是1的正方形的最大边长，得看这三个点dp的最小值，得出状态转移方程式为：

dp(i, j) = min ( dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1) ) + 1
1

代码实现：

public class P221 {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        // 最大边长
        int maxSide = 0;
        // 矩阵行列数
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '0') {
                    // 值为0，则不存在全为1的正方形，int默认值就是0，这里不赋值也行
                    dp[i][j] = 0;
                } else {
                    // 在x轴或者y轴边上，那以其为右下角的正方形，就只能是自己那一块，dp = 1
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        // 否则就走正常的状态转移方程
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                }
                // 求整个矩阵中，每个点的dp的最大值
                maxSide = Math.max(maxSide, dp[i][j]);

            }
        }
        return maxSide * maxSide;
    }
}
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