Đếm số cách đạt điểm trong trò chơi

Xét một trò chơi, trong đó người chơi có thể đạt được điểm số 3, 5 hoặc 10 ở mỗi nước đi. Một điểm mục tiêu cũng được cho. Nhiệm vụ của ta là tìm bao nhiêu cách có thể để đạt được điểm mục tiêu đó với ba giá trị điểm đó.

Theo cách tiếp cận quy hoạch động (dynamic programming), ta sẽ tạo một bảng tất cả điểm từ 0 đến n, và với mỗi giá trị 3, 5, 10, ta đơn giản cập nhật bảng.

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

Đầu vào: Điểm tối đa để đạt được dùng 3, 5 và 10. Giả sử đầu vào là 50.
Đầu ra: Number of ways to reach using (3, 5, 10)50: 14

Thuật toán

countWays(n)
Chỉ có 3 điểm có thể: 3, 5 và 10
Đầu vào: n là điểm tối đa cần đạt.
Đầu ra: Số cách có thể để đạt điểm n.
Bắt đầu
  tạo bảng kích thước n+1
  đặt tất cả mục bảng về 0
  table[0] := 1
  với i := 3 đến n, làm
    table[i] := table[i] + table[i-3]
  kết thúc
  với i := 5 đến n, làm
    table[i] := table[i] + table[i-5]
  kết thúc
  với i := 10 đến n, làm
    table[i] := table[i] + table[i-10]
  kết thúc
  trả về table[n]
Kết thúc

Ví dụ (C++)

#include <iostream>
using namespace std;

// Trả về số cách để đạt điểm n
int countWay(int n) {
  int table[n+1], i;
  // bảng để lưu số lượng cho mỗi giá trị i
  for(int i = 0; i <= n; i++) {
    table[i] = 0; // Khởi tạo tất cả giá trị bảng là 0
  }
  table[0] = 1; // đặt 1 cho đầu vào 0
  for (i = 3; i <= n; i++)
    // thử giải quyết dùng 3
    table[i] += table[i-3];
  for (i = 5; i <= n; i++)
    // thử giải quyết dùng 5
    table[i] += table[i-5];
  for (i = 10; i <= n; i++)
    // thử giải quyết dùng 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