美文网首页动态规划
多重集组合数

多重集组合数

作者: 山有木紫 | 来源:发表于2018-04-02 20:05 被阅读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,所以要减掉

    相关文章

      网友评论

        本文标题:多重集组合数

        本文链接:https://www.haomeiwen.com/subject/nuoxhftx.html