Total Non-Decreasing Numbers with n Digits

Non-Decreasing Number = ตัวเลขที่แต่ละหลัก (ยกเว้นหลักแรก) **ไม่เล็กกว่า** หลักก่อนหน้า (เช่น 111, 112, 123, 789, 569)

ต้องการนับจำนวน Non-Decreasing Numbers ที่มี **n หลัก** (Leading zeros allowed: 001, 012 ถือว่าเป็น 3-digit non-decreasing)

ตัวอย่าง Input และ Output

Input: n = 3
Output: Total non decreasing numbers: 220

อัลกอริทึม Dynamic Programming

ฟังก์ชัน countNumbers(n)

กำหนด:

count[d][len] = จำนวน non-decreasing numbers ความยาว len ที่ **ลงท้ายด้วยหลัก d** (d = 0..9)

Recurrence:

count[d][len] = Σ count[x][len-1] สำหรับ x = 0 ถึง d

เหตุผล: หากลงท้ายด้วย d หลักก่อนหน้าต้อง ≤ d (คือ 0,1,2,...,d)

Base Case:

count[d][1] = 1 สำหรับทุก d (ตัวเลข 1 หลัก มี 1 แบบต่อหลัก)

ขั้นตอน:

1. สร้างตาราง count[10][n+1] เริ่มต้น 0
2. for d = 0..9: count[d][1] = 1
3. for digit = 0..9:
   • for len = 2..n:
     • for x = 0..digit: count[digit][len] += count[x][len-1]
4. คำตอบ = Σ count[d][n] สำหรับ d = 0..9

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

#include <iostream>
#include <algorithm>
using namespace std;

long long int countNumbers(int n) {
    long long int count[10][n+1];
    for(int i = 0; i < 10; i++)
        for(int j = 0; j <= n; j++)
            count[i][j] = 0;

    for (int i = 0; i < 10; i++) count[i][1] = 1;

    for (int digit = 0; digit <= 9; digit++) {
        for (int len = 2; len <= n; len++) {
            for (int x = 0; x <= digit; x++)
                count[digit][len] += count[x][len-1];
        }
    }

    long long int nonDecNum = 0;
    for (int i = 0; i < 10; i++)
        nonDecNum += count[i][n];

    return nonDecNum;
}

int main() {
    int n;
    cout << "Enter number of digits: "; cin >> n;
    cout << "Total non decreasing numbers: " << countNumbers(n);
    return 0;
}

Output

Enter number of digits: 3
Total non decreasing numbers: 220

ความซับซ้อน

• Time: O(10 × 10 × n) = O(n) (คงที่ 100 operations ต่อ n)
• Space: O(n)

สูตรปิด (Closed Form) - Stars and Bars

จำนวน non-decreasing n-digit numbers = จำนวนวิธีเลือก n items จาก 10 types (0-9) แบบ repetition allowed

C(n + 10 - 1, 10 - 1) = C(n + 9, 9)

ตัวอย่าง n=3: C(12,9) = C(12,3) = 220 ✓

ตารางค่าตัวอย่าง