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

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)

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

- Shridhar R Kulkarni

---

你的代码得出3作为结果，因为它将(3, 3, 5)、(3, 5, 3)和(5, 3, 3)看作是不同的组合。 - sudoer

是的，我知道这一点，但我只需要计算不同的组合，而我无法继续。 - Shridhar R Kulkarni

“找零钱”或“硬币找零”是这个问题通常被称为的名称。如果您搜索这个问题，您会在网络和stackoverflow上找到大量资源。 - Paul Hankin

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;

- samgak

---

谢谢！我明白了，关键是强制执行约束。 - Shridhar R Kulkarni

嗨@samgak，我们如何将这种方法转换为自顶向下的动态规划来解决这个问题？（链接：https://stackoverflow.com/questions/50809180/dynamic-programming-number-of-combinations-to-reach-a-given-target） - Diwakar Moturu