动态规划01

第一题：力扣509题

解题思路：

根据题意，定义动态数组，初始化，递推公式，直接遍历就ok！！！

代码如下：

class Solution {
    public int fib(int n) {
        //动态规划典型题目
        if(n <= 1) {
            return n;
        }
        //1. dp数组
        int[] dp = new int[n + 1];
        //3. 初始化
        dp[0] = 0; 
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            //2. 递推公式
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

有个类似的题目：力扣70题

解题思路：

和这个题一模一样，要是说不一样，可能就是dp[0]有点争议？？？

代码如下：

class Solution {
    public int climbStairs(int n) {
        //类似的一道题目509
        if(n <= 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

优化代码如下：

//优化===>维护2个数组就可以了
class Solution {
    public int climbStairs(int n) {
        //类似的一道题目509
        if(n <= 2) {
            return n;
        }
        int[] dp = new int[3];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2]; 
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
}

该题升级版：力扣746题

解题思路：

比这个题多了一个能量的问题，这个题消耗一次能量可以爬上1或者2层楼梯。

代码如下：

class Solution {
    //默认第一个台阶需要花费能量，最后一个台阶不需要
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i < cost.length; i++) {
            //因为消耗一次能量可以上 1 或者 2 个台阶
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        //既然最后一层不消耗能量，那么，就返回前两个小的那一个
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }
}

第二题：力扣62题

解题思路：

和之前的题不太一样的地方就是，这里需要维护一个二维数组来解题，其他的思路还是差不多的。

代码如下：

class Solution {
    public int uniquePaths(int m, int n) {
        //动态规划解题
        //二维数组存放结果
        int[][] dp = new int[m][n];
        //初始化
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++) {
            dp[0][i] = 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];
    }
}

升级版：力扣63题

解题思路：

这个题增加了障碍物，有障碍物就要考虑什么时候更新dp数组了。

代码如下：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //拿到网格的长和宽
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //构建新数组
        int[][] dp = new int[m][n];
        //初始化
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for(int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {
            dp[0][i] = 1;
        }
        //递推公式
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                //如果有障碍物，不更新dp，继续下一个
                if(obstacleGrid[i][j] == 1) {
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

第三题：力扣343题

解题思路：

还是动态规划五大步骤，按照那个来即可！

代码如下：

class Solution {
    public int integerBreak(int n) {
        //dp[i]为正整数i拆分结果的最大乘积
        int[] dp = new int[n+1];
        //初始化，体重已给出，n从2开始
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                //j*(i-j)代表把i拆分为j和i-j两个数相乘
                //j*dp[i-j]代表把i拆分成j和继续把(i-j)这个数拆分，取(i-j)拆分结果中的最大乘积与j相乘
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i-j]));
            }
        }
        return dp[n];
    }
}

第四题：力扣96题

解题思路：

这题可以参考这个，分析的相当清晰，哈哈！！！

代码如下：

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        //初始化
        dp[0] = 1;
        //分别让j从1~i取值，j就是头节点
        for(int i = 1; i <= n; i++) {
            //dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]
            for(int j = 1; j <= i; j++) {
                //dp[j-1] 表示j为头节点的左侧有多少种可能
                //dp[i-j] 表示j为头节点的右侧有多少种可能
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}

说实话，动态规划问题还是比较难理解的呢，接下来可能还有更难理解的呢，坚持下去！！！