Số Lượng Số Không Giảm Có n Chữ Số

Giới thiệu

Số không giảm (non-decreasing) là số mà mỗi chữ số (từ thứ 2) không nhỏ hơn chữ số trước nó. Đếm số lượng số không giảm có n chữ số (có thể bắt đầu bằng 0).

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

Đầu vào: n = 3
Đầu ra: 220 (ví dụ: 111, 112, 123, 789, 569...).

Thuật toán Quy hoạch động

Bảng count[10][n+1]: count[d][len] = số số không giảm độ dài len kết thúc bằng chữ số d. Khởi tạo count[d][1]=1. Công thức: count[d][len] = sum_{x=0..d} count[x][len-1]. Tổng kết quả = sum_{d=0..9} count[d][n].

countNumbers(n)
Begin
    count[10][n+1] = {0}
    for d=0..9: count[d][1]=1
    for d=0..9:
        for len=2..n:
            for x=0..d:
                count[d][len] += count[x][len-1]
    total = sum_{d=0..9} count[d][n]
    return total
End

Ví dụ C++

#include <iostream>
using namespace std;

long long countNumbers(int n) {
    long long count[10][n+1] = {0};
    for (int i=0; i<10; i++) count[i][1] = 1;
    for (int d=0; d<=9; d++) {
        for (int len=2; len<=n; len++) {
            for (int x=0; x<=d; x++)
                count[d][len] += count[x][len-1];
        }
    }
    long long total = 0;
    for (int i=0; i<10; i++) total += count[i][n];
    return total;
}

int main() {
    int n;
    cout << "Nhập số chữ số: "; cin >> n;
    cout << "Tổng số không giảm: " << countNumbers(n);
    return 0;
}

Kết quả

Nhập số chữ số: 3
Tổng số không giảm: 220