2025-12-18小记

周四，理论上是组合的日子，但是还是没有开。

下午先是等组合消息躺了会，然后下来刷题：
也不知道去刷什么，看了排序专题，明明写的是冒泡，我写的也是冒泡，不让过，先放一下吧，他这专题其实好几次了都是这样子，牛头不对马嘴，然后去写动态规划了：

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i=0;i<nums.size();i++)
        {
            sum=sum+nums[i];
        }//这个动态去找一半的思路倒是想到了，但后面怎么找动态规划能找到一半不会了，只会找最大值。
        if(sum%2!=0)
        {
            return false;
        }
        int aim=sum/2;
        vector<bool> dp(aim+1,false);
        dp[0]=true;
        for(int i=0;i<nums.size();i++)
        {
            int num=nums[i];
            // 要么不选当前num，要么选当前num（看dp[j-num]是否可行）
            //主要是看之前的dp[数字]是否已经可以实现，或者之前j-num的数字是否存在，加上num就可以存在的了。
            //像一开始0存在，那么就是当前的0+num就可以存在了，以此类推，后面的数字分别用不同的数字组合，看是否存在
            for(int j=aim;j>=num;j--)
            {
                dp[j]=dp[j]||dp[j-num];
            }
            // 提前终止：如果已经找到能组成target的子集，直接返回
            if(dp[aim])
            {
                return true;
            }
        }
        return false;

    }

看写的形式和之前的0/1背包问题差不多，但是背包会用max，而这边直接用bool数组前存储是否能够组合出不同存在的数字。
看了这个动态规划，其实可以想出是要找出总和的一半来，但是也需要判断是否为偶数来提前看是不是可以分割。
题目本身应该算是NP问题，应该说是有难度的，但是看动态规划也是学习的过程，进一步巩固这个背包问题了。

然后去复习最优化了。

看了一小时左右，去看随机过程，随机过程感觉不会的更多，还是看看习题课件。

晚上python,课上刷了几个最优化的大题，晚上回来就算了吧。