动态规划-达到给定分数的不同组合数

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)

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

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;