爬楼梯(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> generate(int numRows) {
        List> res = new ArrayList();
        res.add(new ArrayList(Arrays.asList(1)));
        for (int i = 1; i  layer = new ArrayList();
            layer.add(1);
            for (int j = 1; j 

• 分析

可以看作给每层作dp

打家劫舍(198)

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[];
        for (int i = 0; i 

优化空间

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 

• 分析

两层循环, 内部循环作 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  10000 ? -1 : dp[amount];
    }
}

• 分析

先对coins作sort, 修剪枝叶, 再二层循环

单词拆分(139)

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

        for (int i = 1; i = word.length() && dp[i-word.length()] && word.equals(s.substring(i- word.length(), i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}