01背包 踩坑记

[Draymonders]

起因

参加了一场虚拟比赛，有一道01背包的问题。

但思维定式了，最后看题解发现确实是一样的思路，只是错在了一个点上

• 可被三整除的最大和 leetcode 1262

01 背包模板

for (int i=0; i<n; i++) {
  for (int j=weights; j>=s[i]; j--)
    dp[j] = max(dp[j], dp[j-s[i]] + w[i]);
}

这里的 dp[j] = max(dp[j], dp[j-s[i]] + w[i]) 其实是 dp[i][j] = max(dp[i-1][j], dp[i-1][j-s[i]] + w[i]), 即第i个物品是否加入背包(前者不加入，后者加入)

坑

由于没过脑子 我直接认为 dp[i][j] = max(dp[i][j], dp[i-1][j-s[i]] + w[i])
真的是 差之毫厘，谬以千里.