动态规划

多重集组合数

2018-04-02  本文已影响56人  山有木紫

在挑战程序设计竞赛第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个的组合总数
分为两种情况:

  1. 没有取第i种。dp[i][j]:在前i-1种中取出j个

  2. 取了第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,所以要减掉

上一篇 下一篇

猜你喜欢

热点阅读