动态编程-达到给定分数的不同组合的数量 [英] Dynamic Programming - Number of distinct combinations to reach a given score

问题描述

考虑一个游戏，玩家在移动中可以得分3或5或10分。给定总分数n，找到达到给定分数的不同组合的数量。

Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of 'distinct' combinations to reach the given score.

我的代码：

#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）

For input 11, I am getting 3 as output but distinct combinations possible is only 1. (11 = 3 + 3 + 5)

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

How do I modify the above code to return the number of 'distinct' combination?

推荐答案

您可以通过强制约束每个组合中的元素必须单调递增（即每个元素等于或大于前一个元素）来找到不同的组合）。因此，允许（3，3，5），但不允许（3，5，3）和（5，3，3）。要实现此目的，只需将最小值传递给numOfWays，以指示所有剩余值必须等于或大于此值。

You can find the distinct combinations by enforcing a constraint that the elements in each combination must be monotonically increasing (i.e. each element is equal to or greater than the previous). So (3, 3, 5) is allowed but (3, 5, 3) and (5, 3, 3) are not. To implement this, just pass a minimum value to numOfWays, to indicate that all remaining values must be equal to or greater than this value.

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为单位的唯一索引：

You also need to consider the min when memoizing. You can use tuples, or just compute an unique index in m for every combination of n and min:

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

最初拨打电话时的分钟数为1（3也可以，但1是更通用的电话）：

Call initially with a min of 1 (3 would also work but 1 is more general purpose):

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

这篇关于动态编程-达到给定分数的不同组合的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！