动态规划

如果某一问题有很多重叠子问题，使用动态规划是最有效的

解题步骤：

背包问题：01背包，完全背包，多重背包

01背包：
统一使用一维数组来进行遍历

 public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                //对于组合问题的递推公式为：dp[j] += dp[j - nums[i]]，需要初始化dp[0]=1;
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }

完全背包：

01背包和完全背包唯一不同就是体现在遍历顺序上,完全背包的物品是可以添加多次的，所以要从小到大去遍历
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        //对于组合问题的递推公式为：dp[j] += dp[j - nums[i]]，需要初始化dp[0]=1;
    }
}
//对于排列问题，先遍历背包，再遍历物品
dp[0] = 1;
for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

509、斐波那契数

class Solution {
    public int fib(int n) {
        // if(n==1){
        //     return 1;
        // }
        // if(n==0){
        //     return 0;
        // }
        // return fib(n-1)+fib(n-2);
        if(n==1){
            return 1;
        }
        if(n==0){
            return 0;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i < n+1; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

70、爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n==1) 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];
    }
}

746、使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= cost.length; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}

62、 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for(int i = 1; i < m; i++){
            dp[i][0] = 1;
        }
        for(int j = 1; j < n; j++){
            dp[0][j] = 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、不同路径 II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        if(obstacleGrid[0][0] == 1){
            return 0;
        }else{
            dp[0][0] = 1;
        }
        for(int i = 1; i < m; i++){
            if(obstacleGrid[i][0] == 1){
                break;
            }else{
                dp[i][0] = 1;
            }
        }
        for(int j = 1; j < n; j++){
            if(obstacleGrid[0][j] == 1){
                break;
            }else{
                dp[0][j] = 1;
            }
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] == 1){
                    continue;
                }else{
                    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) {
        // 方法一：贪心
        // if(n == 2){
        //     return 1;
        // }else if(n == 3){
        //     return 2;
        // }
        // int result = 1;
        // while(n > 0){
        //     if(n > 4){
        //         result *= 3;
        //         n = n - 3;
        //     }else if(n == 4){
        //         result *= 4;
        //         break;
        //     }else if(n == 3 || n == 2){
        //         result *= n;
        //         break;
        //     }
        // }
        // return result;
        // 方法二：动态规划
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i < n; i++){
            int left = 0;
            int right = i - 1;
            while(left <= right){
                dp[i] = Math.ma