当前位置：首页 > article >正文

力扣动态规划-25【算法学习day.119】

article 2025/2/10 22:42:53

前言

###我做这类文章一个重要的目的还是记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.分割等和子集

题目链接:416. 分割等和子集 - 力扣（LeetCode）

题面:

代码:

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = 0;
        for(int a:nums){
            n++;
            sum+=a;
        }
        if(sum%2==1){
            return false;
        }
        int[][] f = new int[n+1][sum+1];
        Arrays.fill(f[0],-1);
        f[0][0] = 0;
        for(int i = 1;i<=n;i++){
            System.arraycopy(f[i - 1], 0, f[i], 0, sum + 1);
            for(int j = nums[i-1];j<=sum;j++){
                if (f[i - 1][j - nums[i-1]] < 0) {
                    continue;
                }
                f[i][j] = Math.max(f[i][j], f[i - 1][j - nums[i-1]] + 1);
            }
        }
        return f[n][sum/2]>0;

    }
}