Thuật toán để tìm số các số tự nhiên ko giảm nhỏ hơn số không giảm N?

[D_ng_Ph_m (Dương Phạm)]

Cụ thể đề bài như sau ạ :
Một số được gọi là không giảm nếu các chữ số từ trái qua phải chỉ đơn điệu tăng hoặc bằng nhau.

Ví dụ:

123 là số không giảm
11123333 là số không giảm
112343 không phải số không giảm
Bài toán đặt ra là cho một số nguyên N, hãy xác định đó có phải là số không giảm hay không. Nếu đúng thì đếm số lượng các số không giảm nhỏ hơn N.

[Gio (Gió)]

Đầu tiên tìm thuật toán của số không giảm có độ dài n, có chữ số bắt đầu là st kết thúc là nd.

ví dụ số không giảm có 2 chữ số [00] -> [99]

Nhận thấy số chữ số hình thành là tổ hợp lặp

[0 1 2 3 4 # 5 # 6 7 8 9] lấy 2 vị trí

nên số cách hình thành là C_nd-st+nⁿ= 55 số

Giờ xây dựng thuật toán cho số a( lưu với vector chứa các chữ số )

function dem(v, st=0)
  res=0
  n=length(v)
  for i in range(st,v[0]):
    res+=C(9-i+n-1,n-1) ## đếm số không giảm mà có chữ số thứ n nhỏ hơn trong a
  res+=dem(v[1:],v[0])
  return res
end

[D_ng_Ph_m (Dương Phạm)]

conver sang C giúp mk với

[Gio (Gió)]

Code demo

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef long long ll;

ll gt[20];

ll C(int n,int k){  // to hop k n phan tu
     return gt[n]/gt[k]/gt[n-k];
}
ll dem(char *v,int n,int st){
     if(n==0) return 0;
     ll res=0;
     int i;
     for(i=st;i<v[0]-'0'; i++){
             res+=C(9-i+n-1,n-1);
     }
     res+=dem(v+1,n-1,v[0]-'0');
     return res;
}
int main(){
    int i;
    gt[0]=1;
    for(i=1;i<20;++i) gt[i]=gt[i-1]*i;
    char so[25]; // so khong giam
    scanf("%s",so);
    int n=strlen(so);
    printf("%lld\n", dem(so,n,0));
    return 0;
}