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];}
}