dp[j] = max(dp[j], dp[j - v[i]] + w[i])
假如枚举到:i = 3, j = 8, v[3] = 5, w[3] = 1
二维:dp[3][8] = max(dp[2][8], dp[2][3] + w[3]) 此时的dp[2][8]和dp[2][3]都是上一轮的状态值
一维:dp[8] = max(dp[8], dp[3] + w[3]) 我们要保证dp[8]和dp[3]都是上一轮的状态值
按照逆序的顺序,一维dp数组的更新顺序为:dp[8], dp[7], dp[6], ... , dp[3]
也就是说,在本轮更新的值,不会影响本轮中其他未更新的值!较小的index对应的状态是上一轮的状态值!
如果按照顺序进行更新,dp[3] = max(dp[3], dp[0] + w[0]),对dp[3]的状态进行了更新,那么在更新dp[8]时,用到的dp[3]
就不是上一轮的状态了,不满足动态规划的要求。
作者:polaris
链接:https://www.acwing.com/solution/content/3982/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。