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;
}
}打家劫舍
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;
}
}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,那么没有解码方法，
直接返回一个0
if (s.charAt(i) == '0') {
return 0;
} else {
//不然就返回一个1
dp[i] = 1;
}
} else {
//对于第二个数开始，下标为1的数字
if (s.charAt(i) != '0') {
//给它赋一个初值
dp[i] = dp[i - 1];
}
//如果说它和前面一个数满足在10-26之间，首先前一个数等于1或者2，其次它的值要小于26
if (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];
}
}
官方题解:
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)); // 输出: ellLCR 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; // 不选取任何元素时，和为0
for (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];
}
}同上
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];
}
}