在挑战程序设计竞赛第69页
公式
dp[i+1][j] = dp[i][j] + dp[i+1][j-1] - dp[i][j-1-a[i]]
的解释:
dp[i+1][j]:从前i种物品中取出j个的组合总数
分为两种情况:
-
没有取第i种。dp[i][j]:在前i-1种中取出j个
-
取了第i种。
dp[i+1][j-1]:先从第i种取一个,再从前i种中取j-1个。但是这样包含了取了a[i]+1个第i种的情况,所以要减掉
dp[i][j-1-a[i]]:在前i-1种中只取了j-1-a[i],这样在第i中就要取a[i]+1,所以要减掉
网友评论