计算游戏中达到给定分数的方式数量

让我们考虑一个游戏，在该游戏中，玩家每步动作可以得到3、5或10的分数。还给出目标分数。我们的任务是找到用这三个点来达到目标分数的可能方法。

通过动态编程方法，我们将创建一个从0到n的所有得分的列表，并且对于3、5、10的每个值，我们只需更新表即可。

输入输出

Input:
The maximum score to reach using 3, 5 and 10. Let the input is 50.
Output:
Number of ways to reach using (3, 5, 10)50: 14

算法

countWays(n)

只有3分，分别是3、5和10

输入：  n是要达到的最高分数。

输出-达到分数n的可能方法的数量。

Begin
   create table of size n+1
   set all table entries to 0
   table[0] := 1

   for i := 3 to n, do
      table[i] := table[i] + table[i-3]
   done

   for i := 5 to n, do
      table[i] := table[i] + table[i-5]
   done

   for i := 10 to n, do
      table[i] := table[i] + table[i-10]
   done

   return table[n]
End

示例

#include <iostream>
using namespace std;

//返回达到分数n的方法数量
int countWay(int n) {
   int table[n+1], i;    //table to store count for each value of i

   for(int i = 0; i<=n; i++) {
      table[i] = 0;    // Initialize all table values as 0
   }

   table[0] = 1;       //set for 1 for input as 0
   for (i=3; i<=n; i++)    //try to solve using 3
      table[i] += table[i-3];

   for (i=5; i<=n; i++)    //try to solve using 5
      table[i] += table[i-5];

   for (i=10; i<=n; i++)    //try to solve using 10
      table[i] += table[i-10];

   return table[n];
}

int main() {
   int n;
   cout << "Enter max score: ";
   cin >> n;
   cout << "Number of ways to reach using (3, 5, 10)" << n <<": " << countWay(n);
}

输出结果

Enter max score: 50
Number of ways to reach using (3, 5, 10)50: 14