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

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

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

来源

2016-06-16 Shridhar R. Kulkarni

你的代码给出了3作为ans，因为它将（3，3，5），（3,5，3）和（5，3，3）计数为不同的组合。 – sudoer

是的，我知道它，但我需要只计算不同的组合，我无法继续。 –

“硬币改变”或“改变”是这个问题经常出现的名称。如果你搜索的话，你会在网络上找到大量的资源。 –

您可以通过强制约束条件来找到不同的组合，即每个组合中的元素必须单调递增（即每个元素等于或大于前一个）。所以（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;

您还需要memoizing时，考虑到分钟。您可以使用元组，或只计算为m的唯一索引n和分钟的每个组合：

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

用1分钟通话开始（3也将工作，但1是更通用的）：

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

来源

2016-06-16 05:21:25 samgak

谢谢！我得到了，关键是强制执行约束。 –

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

回答

相关问题