hot100之动态规划上

爬楼梯(070)

1. class Solution {
2.     int[] memo = new int[50];
3.     public int climbStairs(int n) {
4.         if (memo[n] != 0) return memo[n];
5.         if (n == 0  || n ==1 ){
6.             return 1;
7.         }
8.         if (n == 2){
9.             return 2;
10.         }
12.         memo[n] = climbStairs(n-1) + climbStairs(n-2);
13.         return memo[n];
14.     }
15. }

复制代码

• 废话
  

这题真是从小做到大
感觉动态规划就好像 递归的记忆化
杨辉三角(118)

1. class Solution {
2.     public List<List<Integer>> generate(int numRows) {
3.         List<List<Integer>> res = new ArrayList<>();
4.         res.add(new ArrayList<>(Arrays.asList(1)));
5.         for (int i = 1; i < numRows; i++){
6.             List<Integer> layer = new ArrayList<>();
7.             layer.add(1);
8.             for (int j = 1; j < i; j++){
9.                 layer.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
10.             }
11.             layer.add(1);
12.             res.add(layer);
13.         }
14.         return res;
15.     }
16. }

复制代码

• 分析
  

可以看作给每层作dp
打家劫舍(198)

1. class Solution {
2.     public int rob(int[] nums) {
3.         int n = nums.length;
4.         int[] dp = new int[];
5.         for (int i = 0; i < n; i++){
6.             dp[i+2] = Math.max(dp[i]+nums[i], dp[i+1]);
7.         }
8.         return dp[n+1];
9.     }
10. }

复制代码

优化空间

1. class Solution {
2.     public int rob(int[] nums){
3.         int dp_0 = 0;
4.         int dp = 0;
5.         for (int num : nums){
6.             int dp_new = Math.max(dp, dp_0 + num);
7.             dp_0 = dp;
8.             dp = dp_new;
9.         }
10.         return dp;
11.     }
12. }

复制代码

• 分析
  

dp[0]与dp[1]作为基础态
因为dp要由dp[i-1]和dp[i-2]共同决定 dp[0]与dp[1]前置条件不足
优化空间
因为dp只由dp[i-1]和dp[i-2]决定, 返回结果也只需要最终值
通过dp_0  dp 保存所需前状态

• 感悟
  

dp保存[0,i-2]区间能赚到的最大值
完全平方数(279)

[code]class Solution {    public int numSquares(int n) {        int[] dp = new int[n+1];        dp[0] = 0;        for (int i = 1; i