sub07 線性DP - O(1) 狀態轉移2_嗶哩嗶哩_bilibili

跳樓梯

class Solution {public int climbStairs(int n) {if (n <= 1) {return 1; // 處理邊界情況}int[] dp = new int[n + 1]; // 創建長度為n+1的數組，比方說跳二級樓梯dp[0] = 1; // 初始值設定dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2]; // 狀態轉移方程}return dp[n]; // 返回結果}
}

跳兩級樓梯，那么有零級，一級這兩種，總共是三種，所以說最后的這個下標就是2，int[n+1]

判異，防止n<=1這種異常情況，去判空

爬樓的最少成本：LCR 088. 使用最小花費爬樓梯 - 力扣（LeetCode）

class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length;int[] arr = new int[len+1];arr[0]=0;arr[1]=0;for(int i=2;i<=len;i++){arr[i]=min((arr[i-1])+cost[i-1],(arr[i-2]+cost[i-2]));}return arr[len];}public int min(int num1,int num2){return num1>num2? num2:num1;}
}

打家劫舍

LCR 089. 打家劫舍 - 力扣（LeetCode）

class Solution {public int rob(int[] nums) {int len = nums.length;int[] num= new int[len];num[0]=nums[0];for(int i=1;i<len;i++){if(i==1){num[i]=max(nums[0],nums[1]);}else{num[i]=max((num[i-2]+nums[i]),num[i-1]);}}return num[len-1];}public int max(int num1,int num2){return num1>num2?num1:num2;}
}

LCR 090. 打家劫舍 II - 力扣（LeetCode）

class Solution {public int rob(int[] nums) {int n = nums.length;if(n == 1){return nums[0];}else if(n == 2){return max(nums[0],nums[1]);}int[][] dp = new int[n][2];//第二個下標為0表示選擇不選第一個數字dp[0][0]=0;dp[0][1]=nums[0];dp[1][0]=nums[1];dp[1][1]=nums[0];for(int i = 2;i<n;i++){for(int j =0;j<2;j++ ){if(j == 1 && i == n-1){dp[i][j]=dp[i-1][j];}else{dp[i][j]=max(dp[i-2][j]+nums[i],dp[i-1][j]);}}}return max(dp[n-1][0],dp[n-1][1]);}public int max(int a,int b){return a>b?a:b;}
}

91. 解碼方法 - 力扣（LeetCode）

class Solution {public int numDecodings(String s) {int n = s.length();int[] dp = new int[n];for (int i = 0; i < n; i++) {if (i == 0) {//首先對初始值進行處理，如果說第1個數就是0,那么沒有解碼方法，
直接返回一個0if (s.charAt(i) == '0') {return 0;} else {//不然就返回一個1dp[i] = 1;}} else {//對于第二個數開始，下標為1的數字if (s.charAt(i) != '0') {//給它賦一個初值dp[i] = dp[i - 1];}//如果說它和前面一個數滿足在10-26之間，首先前一個數等于1或者2，其次它的值要小于26if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {//這是求映射的技巧int val = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');if (val <= 26) {if (i == 1) {dp[i]++;} else {dp[i] += dp[i - 2];}}}}}return dp[n - 1];}
}

1646. 獲取生成數組中的最大值 - 力扣（LeetCode）

class Solution {public int getMaximumGenerated(int n) {int[] dp = new int[n + 1];//先定義一個長度為n+1的數組if (n == 0) {return 0;} else if (n == 1) {return 1;}dp[0] = 0;dp[1] = 1;int maxDp  =  dp[1];for(int i = 2;i<=n;i++){if(i%2 == 0){dp[i]=dp[i/2];}else{dp[i] = dp[(i-1)/2]+dp[(i-1)/2+1];}maxDp = max(dp[i],maxDp);}//不應該只是比較最后幾個數return maxDp;}public int max(int a, int b) {return a > b ? a : b;}
}

1043. 分隔數組以得到最大和 - 力扣（LeetCode）

class Solution {public int maxSumAfterPartitioning(int[] arr, int k) {int len = arr.length;int[] dp = new int[len];for (int i = 0; i < len; i++) {int maxValue = 0;//因為這個maxValue要在下面這個循環中重復使用for (int j = i; j >= i - k + 1 && j >= 0; --j) {//取分組中的最大值maxValue = Math.max(arr[j], maxValue);if (j == 0) {dp[i] = Math.max(dp[i], +maxValue * (i - j + 1));} else {dp[i] = Math.max(dp[i], dp[j - 1] + maxValue * (i - j + 1));}}}return dp[len - 1];}
}

139. 單詞拆分 - 力扣（LeetCode）

官方題解:

public class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordDictSet = new HashSet(wordDict);boolean[] dp = new boolean[s.length() + 1];dp[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i; j++) {if (dp[j] && wordDictSet.contains(s.substring(j, i))) {dp[i] = true;break;}}}return dp[s.length()];}
}作者：力扣官方題解
鏈接：https://leetcode.cn/problems/word-break/solutions/302471/dan-ci-chai-fen-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

上述相同，也是判斷前j個是不是真，然后判斷j-i,是不是真，真的話就跳出循環子循環

轉化成Set的作用是提高查找效率

class Solution {public boolean wordBreak(String s, List<String> wordDict) {int len = s.length();Set<String> set = new HashSet(wordDict);boolean[] dp = new boolean[len];for (int i = 0; i < len; i++) {for (int j = i; j >= 0; j--) {if (j == 0) {if (set.contains(s.substring(j, i+1))) {dp[i] = true;break;}} else {if (dp[j-1] && set.contains(s.substring(j, i + 1))) {dp[i] = true;break;}}}}return dp[len - 1];}}

?substring用法substring[i,j),要選擇第j到第i個的元素，用substring(j,i+1）

String s = "hello";// 截取索引1到索引3（不包含）之間的字符，得到"el"
System.out.println(s.substring(1, 3));  // 輸出: el// 截取索引1到索引4（不包含）之間的字符，得到"ell"
System.out.println(s.substring(1, 4));  // 輸出: ell// 截取索引0到索引5（不包含）之間的字符，也就是整個字符串
System.out.println(s.substring(0, 5));  // 輸出: hello// 如果要截取從索引j到索引i（包含i）的字符，就需要使用i+1作為endIndex
int j = 1;
int i = 3;
System.out.println(s.substring(j, i + 1));  // 輸出: ell

LCR 101. 分割等和子集 - 力扣（LeetCode）

class Solution {public boolean canPartition(int[] nums) {int sum = 0;int len = nums.length;for (int i = 0; i < len; i++) {sum += nums[i];}if (sum % 2 == 1) {return false;}int target = sum / 2;boolean[] dp = new boolean[target + 1];dp[0] = true; // 不選取任何元素時，和為0for (int i = 0; i < len; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = dp[j] || dp[j - nums[i]];}}return dp[target];}
}

416. 分割等和子集 - 力扣（LeetCode）

同上

LCR 103. 零錢兌換 - 力扣（LeetCode）

class Solution {public int coinChange(int[] coins, int amount) {if(amount == 0){return 0;}int len = coins.length;int[] dp = new int[amount+1];dp[0] = 0;// 正確初始化dp數組//因為后面要去取min值所以要去賦最大值for(int i = 1; i <= amount; i++){dp[i] = Integer.MAX_VALUE;}for(int i = 0; i < len; i++){for(int j = coins[i]; j <= amount; j++){// 狀態轉移方程if(dp[j - coins[i]] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}// 檢查是否有解return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
}