นับจำนวนที่มีผลรวมตัวเลขเท่ากับค่าที่กำหนด

กำหนดจำนวนหลัก n และค่าเป้าหมาย sum ต้องการหาจำนวนตัวเลข n หลักที่ผลรวมของตัวเลขแต่ละหลักเท่ากับ sum (ไม่นับ 0 เป็นหลักแรก)

ข้อจำกัด: n = 1 ถึง 100, sum = 1 ถึง 500

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

Input: จำนวนหลัก = 3, ผลรวม = 15
Output: Number of values: 69
(มีตัวเลข 3 หลัก 69 ตัวที่ผลรวมตัวเลข = 15)

อัลกอริทึม

count(digit, sum) - ฟังก์ชันเรียกซ้ำพร้อม Memoization

Begin
  if digit = 0 then return (sum = 0)
  if memTable[digit, sum] ไม่ว่าง then return memTable[digit, sum]
  
  answer := 0
  for i := 0 ถึง 9 do
    if sum - i >= 0 then
      answer := answer + count(digit - 1, sum - i)
    end if
  done
  
  return memTable[digit, sum] := answer
End

numberCount(digit, sum) - ฟังก์ชันหลัก (หลักแรกไม่เป็น 0)

Begin
  สร้าง memTable และตั้งค่าเริ่มต้น -1
  res := 0
  for i := 1 ถึง 9 do  // หลักแรก 1-9
    if sum - i >= 0 then
      res := res + count(digit - 1, sum - i)
    end if
  done
  return res
End

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

#include <iostream>
#define ROW 101
#define COL 501
using namespace std;

unsigned long long int memTable[ROW][COL];

unsigned long long int count(int digit, int sum) {
  if (digit == 0) return sum == 0;
  if (memTable[digit][sum] != -1) return memTable[digit][sum];
  
  unsigned long long int ans = 0;
  for (int i = 0; i < 10; i++)
    if (sum - i >= 0)
      ans += count(digit - 1, sum - i);
  
  return memTable[digit][sum] = ans;
}

unsigned long long int numberCount(int digit, int sum) {
  for(int i = 0; i < ROW; i++)
    for(int j = 0; j < COL; j++)
      memTable[i][j] = -1;
  
  unsigned long long int result = 0;
  for (int i = 1; i <= 9; i++)
    if (sum - i >= 0)
      result += count(digit - 1, sum - i);
  
  return result;
}

int main() {
  int digit, sum;
  cout << "Enter digit count: "; cin >> digit;
  cout << "Enter Sum: "; cin >> sum;
  cout << "Number of values: " << numberCount(digit, sum);
}

ผลลัพธ์

Enter digit count: 3
Enter Sum: 15
Number of values: 69