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

让我们考虑这样一个游戏，其中玩家每走一步可以得到 3、5 或 10 分。还给出了一个目标分数。我们的任务是找出有多少种可能的方法可以用这三个点达到目标分数。

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

输入和输出

输入:
使用 3、5 和 10 达到的最高分数。假设输入为 50。
输出:
使用 (3, 5, 10)50 达到的方法数:14

算法

countWays(n)

只有 3 种可能的分数，分别是 3、5 和 10

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

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

Begin
   创建大小为 n+1 的表
   将所有表条目设置为 0
   table[0] := 1

   对于 i := 3 到 n，执行
      table[i] := table[i] + table[i-3]
   完成

   对于 i := 5 到 n，执行
      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;    //用于存储 i 每个值计数的表

   for(int i = 0; i<=n; i++) {
      table[i] = 0;    // 将所有表值初始化为 0
   }

   table[0] = 1;       //将输入设置为 0 时设置为 1
   for (i=3; i<=n; i++)    //尝试使用 3 进行求解
      table[i] += table[i-3];

   for (i=5; i<=n; i++)    //尝试使用 5 来解决
      table[i] += table[i-5];

   for (i=10; i<=n; i++)    //尝试使用 10 来解决
      table[i] += table[i-10];

   return table[n];
}

int main() {
   int n;
   cout << "输入最高分数:";
   cin >> n;
   cout << "使用 (3, 5, 10) 到达的方法数<< n <<": " << countWay(n);
}

输出

输入最高分数:50
使用 (3, 5, 10) 到达的方法数 50:14

相关文章

• 计算游戏中达到给定分数的方法数
• 盒子堆叠问题