深入理解动态规划解决子集和问题

让我用更直观的方式解释为什么通过做差更新DP表可以得到结果。我会用具体的例子和步骤来详细说明。

基本概念

想象一下，我们有一个背包，我们需要判断是否能恰好装进总重量为sum的物品。每个物品的重量就是数组中的一个数字。

DP表dp[j]表示：​是否可以通过选择前i个物品中的一些，使得总重量恰好为j。

详细步骤解析

让我们用一个具体的例子来说明：nums = [1, 2, 3], sum = 6

初始化阶段

vector<bool> dp(sum + 1, false);
dp[0] = true;  // 空集的和为0

初始状态：

dp = [true, false, false, false, false, false, false]

这表示：不使用任何数字，我们可以得到和为0

处理第一个数字：1

for (int j = sum; j >= num; j--) 
{
    if (dp[j - num]) 
    {
        dp[j] = true;
    }
}

处理过程：

j=6: 检查dp[6-1]=dp[5]=false → 不更新

j=5: 检查dp[5-1]=dp[4]=false → 不更新

j=4: 检查dp[4-1]=dp[3]=false → 不更新

j=3: 检查dp[3-1]=dp[2]=false → 不更新

j=2: 检查dp[2-1]=dp[1]=false → 不更新

j=1: 检查dp[1-1]=dp[0]=true → 设置dp[1]=true

更新后：

dp = [true, true, false, false, false, false, false]

这表示：使用数字1，我们可以得到和为1

处理第二个数字：2

for (int j = sum; j >= num; j--) 
{
    if (dp[j - num]) 
    {
        dp[j] = true;
    }
}

处理过程：

j=6: 检查dp[6-2]=dp[4]=false → 不更新

j=5: 检查dp[5-2]=dp[3]=false → 不更新

j=4: 检查dp[4-2]=dp[2]=false → 不更新

j=3: 检查dp[3-2]=dp[1]=true → 设置dp[3]=true

j=2: 检查dp[2-2]=dp[0]=true → 设置dp[2]=true

更新后：

dp = [true, true, true, true, false, false, false]

这表示：

使用数字2，我们可以得到和为2

使用数字1和2，我们可以得到和为3

处理第三个数字：3

for (int j = sum; j >= num; j--) 
{
    if (dp[j - num]) 
    {
        dp[j] = true;
    }
}

处理过程：

j=6: 检查dp[6-3]=dp[3]=true → 设置dp[6]=true

j=5: 检查dp[5-3]=dp[2]=true → 设置dp[5]=true

j=4: 检查dp[4-3]=dp[1]=true → 设置dp[4]=true

j=3: 检查dp[3-3]=dp[0]=true → 设置dp[3]=true

更新后：

dp = [true, true, true, true, true, true, true]

这表示：我们可以得到所有从0到6的和

为什么做差更新有效？

关键理解：​dp[j - num]表示的是"不使用当前数字num时，能否得到和j-num"​​

当我们检查dp[j - num]时：

如果它为true，意味着存在一个子集，其和为j - num

那么，如果我们选择当前数字num，就可以得到和为(j - num) + num = j

因此，我们可以设置dp[j] = true

为什么需要逆向遍历？

逆向遍历是为了避免重复使用同一个数字。

假设我们正向遍历（从小到大）：

处理数字1：设置dp[1]=true

处理数字2：当j=3时，检查dp[3-2]=dp[1]=true → 设置dp[3]=true

处理数字3：当j=6时，检查dp[6-3]=dp[3]=true → 设置dp[6]=true

看起来也能得到正确结果，但这是因为我们的数字都是正数且没有重复使用的问题。

但如果数字可以重复使用，或者我们需要考虑组合情况，正向遍历就会出错。

​逆向遍历保证了我们在更新dp[j]时，dp[j - num]还没有被当前数字更新过，也就是说，dp[j - num]表示的是不考虑当前数字时的状态。

完整代码再实现

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int n, sum;
	cin >> n >> sum; 
	vector<int> nums(n);
	for (int i = 0; i < n; i++)
	{
		cin >> nums[i];
	}
	
	if (sum == 0) // 目标和为0不可能被实现，输出NO 
	{
		cout << "NO" << endl;
		return 0;
	}
	
	int total = 0;
	
	for (int num : nums)
	{
		total += num;
	}
	
	if (sum > total) // 目标和大于数字总和直接输出NO 
	{
		cout << "NO" << endl;
		return 0;
	}
	else if (sum == total) // 数字总和与目标和相等则直接输出YES 
	{
		cout << "YES" << endl;
		return 0;
	}
	
	vector<bool> DP(sum + 1, false);
	DP[0] = true;
	
	// DP列表表示能凑出来的和，若DP[i] = true这说明i可以被nums中的某些数字凑出来 
	
	for (int num : nums)
	{
		for (int j = sum; j >= num; j--)
		{
			// j作为目标总和时，与当前num的差可以被凑出来（之前某些数的和）即 j = num + 之前某些数字的和，
			// 则说明 j 可以被凑出来，记录在DP表中 
			if (DP[i - num])
			{
				DP[i] = true;
			}
		}
	}
	
	// 查询DP表，若sum被标记了可以被凑出来（标记为true），则输出YES 
	if (DP[sum])
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	return 0;
}