Đếm số cách để đạt được một số điểm nhất định trong một trò chơi

Chúng ta hãy xem xét một trò chơi, trong đó một người chơi có thể nhận được một số điểm với 3, 5 hoặc 10 trong mỗi nước đi. Một số điểm mục tiêu cũng được đưa ra. Nhiệm vụ của chúng ta là tìm ra bao nhiêu cách khả thi để đạt được điểm mục tiêu với ba điểm đó.

Bằng cách tiếp cận lập trình động, chúng tôi sẽ tạo một danh sách tất cả các điểm từ 0 đến n và đối với mỗi giá trị 3, 5, 10, chúng tôi chỉ cần cập nhật bảng.

Đầu vào và Đầu ra

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

Thuật toán

countWays(n)

Chỉ có 3 điểm khả thi, đó là 3, 5 và 10

Đầu vào: n là số điểm tối đa đạt được.

Đầu ra - Số cách có thể để đạt được điểm 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

Ví dụ

#include <iostream>
using namespace std;

// Returns number of ways to reach score 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);
}

Đầu ra

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