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

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;