动态规划

---

70. 爬楼梯

class Solution {
    public int climbStairs(int n) {
        // 1 1 2 3
        int f1 = 1, f2 = 1, f3 = 2;
        while (n-- != 0) {
            f1 = f2;
            f2 = f3;
            f3 = f1 + f2;
        }
        return f1;
    }
}

118. 杨辉三角

// 方法一：类似二维数组，每次new一行
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>(i + 1);
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
                }
            }
            ans.add(row);
        }

        return ans;
    }
}
// 方法二：后面元素由前一个元素公式递推，row[i][j] = a[i][j-1] * (i - j + 1) / j，注意int范围
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>(i + 1);
            row.add(1);
            for (int j = 1; j <= i; j++) {
                row.add((int) ((long) row.get(j - 1) * (i - j + 1) / j));
            }
            ans.add(row);
        }

        return ans;
    }
}

198. 打家劫舍

class Solution {
    public int rob(int[] nums) {
        //      1 2 3 1
        //  偷  1 2 4 3
        //不偷  0 1 2 4
        int steal = 0, notsteal = 0, temp;
        for(int num : nums){
            temp = steal;
            steal = notsteal + num;                 // 选择偷，之前不偷的最大值加上这次偷
            notsteal = Math.max(temp, notsteal);    // 选择不偷，之前偷与不偷的最大值
        }
        return Math.max(steal, notsteal);
    }
}

322. 零钱兑换

// 改自灵神的，根据硬币更新结果，放在外层
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // 取值范围[0,amount]
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] != amount + 1 ? dp[amount] : -1; // 如果没有变过，说明无法兑换，-1
    }
}