欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

背包-力扣-java

程序员文章站 2022-07-16 09:50:54
...

背包-力扣-java

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/

 背包-力扣-java

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

 

相关标签: 背包