背包-力扣-java
程序员文章站
2022-07-16 09:50:54
...
class Solution {
public boolean canPartition(int[] nums) {
int sum=0;
for(int num:nums)
sum+=num;
if(sum%2==1) return false;
sum=sum/2;
int len=nums.length;
boolean[][] dp = new boolean[len+1][sum+1];
for(int i=0;i<=len;i++) dp[i][0]=true;
for(int i=1;i<=len;i++){
for(int j=1;j<=sum;j++){
if(j<nums[i-1]){ //// 背包容量不足,不能装入第 i 个物品
dp[i][j]=dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
}
return dp[len][sum];
}
}
//https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-bian-ti-zhi-zi-ji-fen-ge-by-lab/
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
//可以类比于背包问题
int n=s.length();
//pointer[i]表示s中以i-1结尾的字符串是否可以被拆分
boolean[] pointer=new boolean[n+1];
pointer[0]=true;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
if(pointer[j]&&wordDict.contains(s.substring(j,i))){
pointer[i]=true;
break;
}
}
}
return pointer[n];
}
}
推荐阅读
-
【力扣算法】【python】对角线遍历
-
关于力扣第一题 ---两数之和(多方法)
-
力扣-11.9-46
-
力扣刷题笔记:1052.爱生气的书店老板(普通滑窗题,巧妙利用grumpy[i]的0、1值作为flag计算满意顾客人数)
-
荐 Java BigDecimalの食用方法,老大说我再用Double来进行数值的计算,造成的损失从我工资里扣!˚‧º·(˚ ˃̣̣̥⌓˂̣̣̥ )‧º·˚
-
力扣题目汇总(机器人返回原点,按奇偶排序,数字的补数)
-
力扣题目解答自我总结(二)
-
力扣题目解答自我总结(反转类题目)
-
力扣简单题合集(带答案)
-
力扣OJ 剑指 Offer 68 - II. 236. 二叉树的最近公共祖先