考虑一个游戏，玩家在移动中可以得分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）
如何修改以上代码以返回“不同”组合的数量？
您可以通过强制约束每个组合中的元素必须单调递增（即每个元素等于或大于前一个元素）来找到不同的组合。因此，允许（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;
