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的想法是保留一個表，以避免重新計算相同的子問題。在這種情況下，子問題由您允許使用的分數和最高分數來定義，但解決方案還需要考慮您已經使用了多少兩三和七分，並且如果您還將它們添加到密鑰中，關鍵只會被訪問一次（所以沒有試圖記憶它）。

如果您只需要計數，那麼事情就會有所不同，因爲在這種情況下，子問題的解決方案只是一個數字，您可以使用它來解決原始問題。