动态规划与暴力递归(力扣)

0.动态规划与暴力递归基础

基础理论知识请参考我的算法课程学习之动态规划与暴力递归

1.线性DP

3.递推型DP

所有线性递推关系都可以用矩阵快速幂做，可以达到O(logN)，最典型是斐波那契数列。

斐波那契数列

递推公式遵守F(N) = F(N-1) + F(N-2), 对于第N项，有矩阵乘法的方式可以将时间复杂度降到O(logN)。可以用矩阵的形式，表达递推公式:

递推公式

根据前四列的值，可以推导出:

图片说明

多推倒几次后，可以得到如下通式:

求数列就转化成了，状态矩阵的乘法和幂运算。

矩阵乘法和幂运算

矩阵乘法，要遵守[m,n] * [n,m'], 也就是维度要匹配。新矩阵的(i,j)项是m矩阵的第i行和m'矩阵第j列的内积，所以两个矩阵的维度要匹配，不然无法在这里求内积。

public static long[][] matrixMulti(long[][] m1, long[][] m2) {
    // 矩阵乘法: [m*n] * [n*m'] => m*m'
    int row = m1.length;
    int col = m2[0].length;
    long[][] res = new long[row][col];
    // 填充每一个元素
    for (int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            // res[i][j] = m1中i行的每个元素和m2中j列的每个元素，相乘并相加
            for(int k=0; k<m2.length; k++){
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    return res;
}

矩阵的幂运算，就是多次乘法运算，这里先解释如何快速求10的75次方？

75的二进制形式是1001011
10的75次方=10ˆ64 * 10ˆ8 * 10ˆ2 * 10ˆ1。

在过程一中，先求出10ˆ1, 再根据它平方求出10ˆ2, 再由10ˆ2的平方求出10ˆ4,..., 75的二进制有多少位，就使用几次乘法。
在过程二中，把75对应的二进制上为1的位，累乘所得到的数相乘即可，比如10ˆ64，10ˆ8，10ˆ2， 10ˆ1应该累乘；而32，16，4上对应的累乘数，不相乘。

// temp 被 matrixMulti的结果所更新
public static long[][] matrixPower(long[][] m, long power){
    // 只有方阵有幂运算，结果也是方阵
    long[][] res = new long[m.length][m[0].length];
    // 运算子，每次都要自乘，也就是一次幂已经计算了
    long[][] temp = m;
    // 先把res初始化为单位阵
    for (int i=0; i<m.length; i++){
        res[i][i] = 1;
    }
    // 一个数二进制有多少位: 右移位直到为0的移动次数
    for (; power!=0; power >>= 1){
        // 二进制最低位上是否为0
        // 不为0，则累乘
        if ( (power&1) != 0 ){
            // 这里的temp是n次幂
            res = matrixMulti(res, temp);// 单位矩阵的作用就类似1
        }
        // 更新n次幂，为下次循环做准备
        temp= matrixMulti(temp, temp);
    }
    return res;
}

定义好了上述两个运算，求Fabonacci第N项就是，现将状态矩阵进行N-2次幂运算，再左乘初始状态矩阵[F(2), F(1)]

// 计算Fibonacci数列的第n项
public static long getFibonacciNth(long N){
    // base case:
    if (N == 1 || N == 2){
        return 1;
    }
    long[][] base = { {1,1},
                     {1,0} };
    long[][] res = matrixPower(base, N-2);
    // 1*res[0][0] + 1*res[1][0];
    return res[0][0] + res[1][0];
}

跳台阶(12型求方法数)

奶牛繁殖

4. 贪心策略DP

跳跃游戏2

题号45
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:
请在这里输入引用内容
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

题解思路:
每走出一步中找到最远能达到边界，如果当前位置大于这个边界了，就说明我们不得不跳跃一次，每次跳跃必定是最远的那个。

// 每次尝试走一步，如果走到超出最大边界了，则步数+1，也就是被迫走的每一步都是能达到最大
// 边界的
public static int jump(int[] nums) {
    // 跳的步数
    int step = 0;
    // 跳当前步，最远能达到的地方
    int curRange = 0;
    // 多跳一步，最远能达到的地方，为下一次跳做准备
    int nextRange = -1;
    for (int i = 0; i < nums.length; i++){
        // 不得不跳一步，从之前准备好的最远的，跳那一步
        if ( curRange < i){
            ++step;
            curRange = nextRange;
        }
        // 比如，在i=0的位置上，跳出第一步能达到的最远距离就是 i+nums[i]
        nextRange = Math.max(nextRange, i + nums[i]);
    }
    return step;
}

5. 计数型DP

计数型DP可以以组合数学的方法写出组合数，然后dp求组合数，比如“不同路径I”

不同路径

Nr. 62

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
请在这里输入引用内容
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

解题思路:
创建DP数组，dp[i][j]表示到达(i,j)的方法数，它是由子问题dp[i-1][j]和dp[i][j-1]
注意初始化条件，第一行和第一列都是1，方法数都是1，因为只能直行。

// dp[i][j] 就表示到达(i,j)位置的方法数，它是由子问题，左边和上边的方法数
public static int uniquePaths_DP(int m, int n){
    // 棋盘其实是 n*m
    int[][] dp = new int[n][m];
    int rows = dp.length;
    int cols = dp[0].length;
    // base case: 因为只能向下或者向右，所以第一行，第一列的值都是1，只有一种走法
    // 第一行
    for (int i = 0; i < m; i++){
        dp[0][i] = 1;
    }
    for (int i = 0; i < n; i++){
        dp[i][0] = 1;
    }
    for (int i=1; i<rows; i++){
        for (int j=1; j<cols; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    // 想求board[n-1][m-1]的值
    return dp[rows-1][cols-1];
}

这种依赖左边和上边的可以空间压缩成一个数组。

public static int uniquePaths_DP3(int m, int n){
    int[] dp = new int[m];
    int len = m;
    // 空间压缩
    Arrays.fill(dp, 1);
    for (int row=1; row<n; row++){
        for (int i=1; i<m; i++){
            // In-place 修改空间压缩
            // 等号右边的 dp[i]表示上一次的结果，也就是二维中上面的结果
            // 等号右边的 dp[i-1]表示左边的结果，也就是二维中左面的结果
            dp[i] = dp[i] + dp[i-1];
        }
    }
    return dp[m-1];
}

不同路径II

Nr. 63

一一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
请在这里输入引用内容
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
请在这里输入引用内容
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

解题思路：
和62类似，也是建立DP数组，不过要注意边界条件。第一行和第一列如果遇到障碍物，后面的格子都不可达，所以都是0。如果(i,j)不是障碍物，则dp[i][j]的公式和62一致。

public static int getPaths_DP(int[][] obstacleGrid) {
    if (obstacleGrid == null || obstacleGrid.length==0){
        return 0;
    }
    int rows = obstacleGrid.length;
    int cols = obstacleGrid[0].length;
    // 初始化为0
    int[][] dp = new int[rows][cols];

    // 第一列中，如果不是障碍物有一种方法达到
    // 一旦遇到障碍物后，后续的点都不可到达都为0
    for (int i=0; i<rows && obstacleGrid[i][0] == 0; i++){
        dp[i][0] = 1;
    }

    // 第一行中, 如果不是障碍物有一种方法达到
    // 一旦遇到障碍物后，后续的点都不可到达都为0
    for (int i=0; i<cols && obstacleGrid[0][i] == 0; i++){
        dp[0][i] = 1;
    }

    // general case
    for (int i=1; i<rows; i++){
        for (int j=1; j<cols; j++){
            // 判断是否是障碍物，是障碍物自动置0
            if (obstacleGrid[i][j] == 0){
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
    }
    return dp[rows-1][cols-1];
}

这个空间优化，一定注意边界条件，也就是每次row循环时的第一个数！
并且要先处理第一行。循环从第二行开始。

public static int getPaths_DP2(int[][] obstacleGrid){
    if (obstacleGrid == null || obstacleGrid.length==0){
        return 0;
    }
    int rows = obstacleGrid.length;
    int cols = obstacleGrid[0].length;
    int[] dp = new int[cols];

    // 第一行中, 如果不是障碍物有一种方法达到
    // 一旦遇到障碍物后，后续的点都不可到达都为0
    for (int i=0; i<cols && obstacleGrid[0][i] == 0; i++){
        dp[i] = 1;
    }
    // general case
    for (int i=1; i<rows; i++){
        // 单独处理第一个节点
        // 当上一个是0 或者 当前位置是障碍物，那么第一个位置就是0
        dp[0] = (dp[0]==0 || obstacleGrid[i][0] == 1) ? 0 : 1;
        for (int j=1; j<cols; j++){
            // 如果当前j=0是障碍物，就要手动置零，二维方法中初始化为0
            if (obstacleGrid[i][j] == 1){
                dp[j] = 0;
                //continue;
            }else { // 如果不是障碍物，继承上一个0位置的值
                dp[j] += dp[j-1];
            }
        }
    }
    return dp[cols-1];
}