动态编程-达到给定分数的不同组合的数量

小编典典

动态编程-达到给定分数的不同组合的数量

algorithm

考虑一个游戏，玩家在移动中可以得分3或5或10分。给定总分数n，找到“不同”组合的数量以达到给定分数。

我的代码：

#include <iostream>
#include<unordered_map>
using namespace std;

unordered_map<int,int> m;

int numOfWays(int n){
    if(n==0)
        return 1;
    if(n<0)
        return 0;
    if(m[n]>0)
        return m[n];
    m[n] = numOfWays(n-3)+numOfWays(n-5)+numOfWays(n-10);
    return m[n];
}

int main(){
    int t; 
    cin>>t;
    cout<<numOfWays(t)<<endl;
    return 0;
}

对于输入11，我得到3作为输出，但可能的不同组合仅为1。（11 = 3 + 3 + 5）

如何修改以上代码以返回“不同”组合的数量？

阅读 199

2020-07-28

共1个答案

小编典典

您可以通过强制约束每个组合中的元素必须单调递增（即每个元素等于或大于前一个元素）来找到不同的组合。因此，允许（3，3，5），但不允许（3，5，3）和（5，3，3）。要实现此目的，只需将最小值传递给numOfWays，以指示所有剩余值必须等于或大于该值。

int numOfWays(int n, int min){

计算这种方式的数量：

int ways = 0;
if(min <= 3)
   ways += numOfWays(n-3, 3);
if(min <= 5)
   ways += numOfWays(n-5, 5);
if(min <= 10)
   ways += numOfWays(n-10, 10); // from now on elements must be 10 or greater
m[index] = ways;

在记忆时，您还需要考虑分钟数。您可以使用元组，也可以只为n和min的每种组合计算以m为单位的唯一索引：

int index = (n * 10) + min;
if(m[index]>0)
    return m[index];

最初以最少1的价格拨打电话（3也可以，但1更通用）：

cout<<numOfWays(t,1)<<endl;

2020-07-28