C++中的记忆

Question

给出板球队的比分，找到/打印所有配置/获得比分的方法。有3种方法得分2,3和7

实施例： 评分：10

输出： （0,1,1） （0,2,2） （0,0,5 ）

void out(int score, int two, int three, int seven) 
{ 
    if(score == 0) 
    { 
     cout << "(" << two << ", " << three << ", " << seven << ")" << endl; 
    } 
    else if (score < 0) 
    { 
     return; 
    } 
    else 
    { 
     outputs(score - 7, two, three, seven + 1); 
     outputs(score - 3, two, three + 1, seven); 
     outputs(score - 2, two + 1, three, seven);   
    } 
    return; 
} 

我得到了正确的答案，但有重复，也想使用记忆化，我感到很困惑如何实现 （0，1，1） （0，1，1） （ 2，2，0） （2,2,0） （2,2，0） （2,2，0） （2,2，0） （2,2，0） （5，0,0）

Answer 1

为了避免重复，你需要强加一个排序，例如，如果您之前使用分数3，则不允许使用分数7。

void out(int score, int two, int three, int seven, int maxscore) 
{ 
    ... 
    else { 
     if (maxscore >= 7) output(score-7, two, three, seven+1, 7); 
     if (maxscore >= 3) output(score-3, two, three+1, seven, 3); 
     if (maxscore >= 2) output(score-2, two+1, three, seven, 2); 
    } 
} 

使用记忆化，而不是因为你正在寻找枚举所有的解决方案（不只是算他们）会在这个问题更加复杂（甚至可能不是那么有用）。

memoization的想法是保留一个表，以避免重新计算相同的子问题。在这种情况下，子问题由您允许使用的分数和最高分数来定义，但解决方案还需要考虑您已经使用了多少两三和七分，并且如果您还将它们添加到密钥中，关键只会被访问一次（所以没有试图记忆它）。

如果您只需要计数，那么事情就会有所不同，因为在这种情况下，子问题的解决方案只是一个数字，您可以使用它来解决原始问题。