hot100之动态规划上

爬楼梯(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()];
    }
}