นับวิธีทำคะแนนในเกม (Count Ways to Reach Score)

เกมที่ผู้เล่นทำคะแนนได้ 3, 5, หรือ 10 คะแนนต่อครั้ง กำหนดคะแนนเป้าหมาย n ต้องการหาจำนวนวิธีทำคะแนนรวมเท่ากับ n ได้

ใช้ Dynamic Programming: สร้างตารางเก็บจำนวนวิธีสำหรับคะแนน 0 ถึง n อัปเดตตารางสำหรับแต่ละคะแนนที่เป็นไปได้ (3, 5, 10)

การรับค่าและแสดงผล

Input: คะแนนเป้าหมาย = 50
Output: Number of ways to reach using (3, 5, 10) 50: 14

อัลกอริทึม

countWays(n)

Begin
  สร้างตาราง table ขนาด n+1 เติม 0
  table[0] := 1
  
  for i := 3 ถึง n do table[i] := table[i] + table[i-3] done
  for i := 5 ถึง n do table[i] := table[i] + table[i-5] done
  for i := 10 ถึง n do table[i] := table[i] + table[i-10] done
  
  return table[n]
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

int countWay(int n) {
  int table[n+1];
  for(int i = 0; i <= n; i++) table[i] = 0;
  table[0] = 1;
  
  for (int i = 3; i <= n; i++) table[i] += table[i-3];
  for (int i = 5; i <= n; i++) table[i] += table[i-5];
  for (int i = 10; i <= n; i++) 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