LeetCodeHot100 动态规划 70. 爬楼梯 118. 杨辉三角 198. 打家劫舍 279. 完全平方数 322. 零钱兑换

70. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-100-liked

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];
    }

总结：dp数组的含义是当前台阶有几种方法。
118. 杨辉三角
https://leetcode.cn/problems/pascals-triangle/description/?envType=study-plan-v2&envId=top-100-liked

public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> resList = new ArrayList<>();
        int[][] dp = new int[numRows][numRows];
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j <= i; j++) {
                if (i - 1 >= 0 && j - 1 >= 0){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else {
                    dp[i][j] = 1;
                }
            }
        }
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                list.add(dp[i][j]);
            }
            resList.add(list);
        }
        return resList;
    }

总结：二维dp数组
198. 打家劫舍
https://leetcode.cn/problems/house-robber/description/?envType=study-plan-v2&envId=top-100-liked

public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int max = 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0],nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);
        }
        for (int i = 0; i < dp.length; i++) {
            max = dp[i] > max ? dp[i] : max;
        }
        return max;
    }

总结：dp数组就是到这个屋子能偷的最大的钱，最大的钱看偷不偷当前污渍，偷了就是dp[i-2] + 当前，不偷就是dp[i-1]
279. 完全平方数
https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked

public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i],dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

总结：先把dp全设为i， 再取dp[i]和dp[i-j方]+1 的小者。 i - jj >= 0 就是j从1遍历到根号i。 找到j这里之后 用i-jj 就是剩下的数，再去看这个剩下的数的dp值 ，+1是说要加上找到的这个j这步。
322. 零钱兑换
https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        //加1W代表这个位置是无法凑成的
        Arrays.fill(dp,amount + 10000);
        //记得置0，因为如果你能找到0了，那一定有方案可以凑成了啊
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin){
                    dp[i] = Math.min(dp[i],dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 10000 ? -1 : dp[amount];
    }

总结：dp的初始化是无法到达的数，之后再一步步推。