爬樓梯(070)

class Solution {
    int[] memo = new int[50];
    public int climbStairs(int n) {
        if (memo[n] != 0) return memo[n];
        if (n == 0  || n ==1 ){
            return 1;
        }
        if (n == 2){
            return 2;
        }

        memo[n] = climbStairs(n-1) + climbStairs(n-2); 
        return memo[n];
    }
}

• 廢話

這題真是從小做到大

感覺動態規劃就好像 遞歸的記憶化

楊輝三角(118)

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>(Arrays.asList(1)));
        for (int i = 1; i < numRows; i++){
            List<Integer> layer = new ArrayList<>();
            layer.add(1);
            for (int j = 1; j < i; j++){
                layer.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
            }
            layer.add(1);
            res.add(layer);
        }
        return res;
    }
}

• 分析

可以看作給每層作dp

打家劫舍(198)

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[];
        for (int i = 0; i < n; i++){
            dp[i+2] = Math.max(dp[i]+nums[i], dp[i+1]);
        }
        return dp[n+1];
    }
}

優化空間

class Solution {
    public int rob(int[] nums){
        int dp_0 = 0;
        int dp = 0;
        for (int num : nums){
            int dp_new = Math.max(dp, dp_0 + num);
            dp_0 = dp;
            dp = dp_new;
        }
        return dp;
    }
}

• 分析

dp[0]與dp[1]作為基礎態

因為dp[i]要由dp[i-1]和dp[i-2]共同決定 dp[0]與dp[1]前置條件不足

優化空間

因為dp[i]只由dp[i-1]和dp[i-2]決定, 返回結果也只需要最終值

通過dp_0 dp 保存所需前狀態

• 感悟

dp[i]保存[0,i-2]區間能賺到的最大值

完全平方數(279)

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

• 分析

兩層循環, 內部循環作 i - j * j 遍歷 j的平方

零錢兌換(322)

class Solution {
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int[] dp = new int[amount+1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++){
            int min = 10000;
            for (int coin : coins){
                if (i < coin){
                    dp[i] = min;
                    continue;
                }
                min = Math.min(min, dp[i-coin]);
            }
            dp[i] = min+1;
        }
        return dp[amount] > 10000 ? -1 : dp[amount];
    }
}

• 分析

先對coins作sort, 修剪枝葉, 再二層循環

單詞拆分(139)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++){
            for (String word : wordDict){
                if (i >= word.length() && dp[i-word.length()] && word.equals(s.substring(i- word.length(), i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}