hot100之动态规划上
爬楼梯(070)class Solution {
int[] memo = new int;
public int climbStairs(int n) {
if (memo != 0) return memo;
if (n == 0|| n ==1 ){
return 1;
}
if (n == 2){
return 2;
}
memo = climbStairs(n-1) + climbStairs(n-2);
return memo;
}
}
[*]废话
这题真是从小做到大
感觉动态规划就好像 递归的记忆化
杨辉三角(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 = Math.max(dp+nums, dp);
}
return dp;
}
}优化空间
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与dp作为基础态
因为dp要由dp和dp共同决定 dp与dp前置条件不足
优化空间
因为dp只由dp和dp决定, 返回结果也只需要最终值
通过dp_0dp 保存所需前状态
[*]感悟
dp保存区间能赚到的最大值
完全平方数(279)
class Solution { public int numSquares(int n) { int[] dp = new int; dp = 0; for (int i = 1; i
页:
[1]