[Chưa hoàn thiện] [Quy hoạch động] [CHD] [Codefun] Sum of Digits

Đề bài
Hướng làm
Gọi f[n] là số số có tổng các chữ số bằng s từ 0 đến n, có kết quả res = f[b]-f[a-1].
Phần sau tham khảo của templatetypedef , có sửa lại cho đúng
Gọi dp[n,d,k] là số số có n chữ số, bắt đầu bằng d (d có thể bằng 0) và có tổng các chữ số bằng k, có
dp[0,k,s] = 0
dp[1,s,s] = 1 với 0<=s<=9
dp[1,k,s] = 0 với k<>s hoặc 9<s
dp[1,k,s] = 0 với s<0
dp[d,k,s] = sum {dp[d-1,i,s-k]} với i chạy từ 0 đến 9
Ta tính f[n] như sau
B1: f[n] = sum{dp[l,i,s]} với l là số lượng chữ số của n, i chạy từ 0 đến d[i] với d[i] là chữ số thứ i của n
B2: s = s - d[1]
B3: Với i chạy từ 2 đến n
            Với j chạy từ d[i]+1 đến 9
                 f[n] = f[n] - dp[l-i+1,j,s]
            s = s-d[i]
Code C++