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

Question

考虑一个玩家可以在一次移动中获得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)

如何修改上面的代码以返回'distinct'组合的数量？

Answer 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;