爬樓梯(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()];
}
}
浙公網安備 33010602011771號