数位 DP 的关键
数位动态规划（数位DP）主要用于解决 “在区间 [ L , R ] [L,R] [L,R] 这个范围内，满足某种约束的数字的数量、总和、平方” 这一类问题。
数位 dp 有个通用的套路，就是先采用前缀和思想，将求解 “[l,r]这个区间内的满足约束的数的数量”，转化为 " [ 1 , r ] [1,r] [1,r] 满足约束的数量 - 区间 [ 1 , l − 1 ] [1,l-1] [1,l−1] 满足约束的数量“
所以我们最终要求解的问题通通转化为： [ 1 , x ] [1,x] [1,x] 中满足约束的数量，或者 [ 0 , x ] [0,x] [0,x] 中的满足约束的数量（左边界取决于题目）。
示例问题
分析
根据前缀和的思想，可以将问题转换为：整数 0 ≤ x ≤ n u m 2 0 \le x \le num_2 0≤x≤num2，且 0 ≤ d i g i t _ s u m ( x ) ≤ m a x _ s u m 0 \le digit\_sum(x) \le max\_sum 0≤digit_sum(x)≤max_sum 的数量 - 0 ≤ x ≤ n u m 2 0 \le x \le num_2 0≤x≤num2，且 0 ≤ d i g i t _ s u m ( x ) ≤ m i n _ s u m − 1 0 \le digit\_sum(x) \le min\_sum-1 0≤digit_sum(x)≤min_sum−1 的数量 - ( 0 ≤ x ≤ n u m 1 − 1 0 \le x \le num_1-1 0≤x≤num1−1，且 0 ≤ d i g i t _ s u m ( x ) ≤ m a x _ s u m 0 \le digit\_sum(x) \le max\_sum 0≤digit_sum(x)≤max_sum 的数量 - 0 ≤ x ≤ n u m 1 − 1 0 \le x \le num_1-1 0≤x≤num1−1，且 0 ≤ d i g i t _ s u m ( x ) ≤ m i n _ s u m − 1 0 \le digit\_sum(x) \le min\_sum-1 0≤digit_sum(x)≤min_sum−1 的数量)。
于是，我们现在要求解的问题即：整数 0 ≤ x ≤ y 0 \le x \le y 0≤x≤y 且 0 ≤ d i g i t _ s u m ( x ) ≤ s u m 0 \le digit\_sum(x) \le sum 0≤digit_sum(x)≤sum 的数量。
设 x x x 满足要求的一种情况为： a 1 , a 2 , . . . , a k {a_1,a_2,...,a_k} a1,a2,...,ak，其中 k = y k=y k=y 的位数。为方便比较不妨又设 y y y 的每一位是： { b 1 , b 2 , . . . , b k } \{b_1,b_2,...,b_k\} {b1,b2,...,bk}。
当 0 ≤ a 1 < b 1 0\le a_1<b_1 0≤a1<b1，那么此时产生的是前导 0 数字，后面的 a 2 ∼ a k a_2 \sim a_k a2∼ak 全都可以取 0 ~ 9。
方案的属性：
- 确定到了第几位。原来是第一位，现在确定到了第二位。
- digit_sum。原方案的 digit_sum = 子方案的 digit_sum + a 1 a_1 a1
- 方案数。原方案的方案数 = 子方案的方案数。
于是，分解出的子问题是，后面的 a 2 ∼ a k a_2 \sim a_k a2∼ak 最多只能取到 0 ∼ 9 0 \sim 9 0∼9 满足 sum < digit_sum - a 1 a_1 a1 的方案数。(此处可以进行记忆化)
当 a 1 = b 1 a_1 = b_1 a1=b1，后面的 a 2 ∼ a k a_2 \sim a_k a2∼ak 最多只能取到 b 2 ∼ b k b_2 \sim b_k b2∼bk。
方案的属性：
- 确定到了第几位。原来是第一位，现在确定到了第二位。
- digit_sum。原方案的 digit_sum = 子方案的 digit_sum + a 1 a_1 a1
- 方案数。原方案的方案数 = 子方案的方案数。
于是，分解出的子问题是，后面的 a 2 ∼ a k a_2 \sim a_k a2∼ak 最多只能取到 y = { b 2 , b 3 , . . . , b k } y = \{b_2,b_3,...,b_k\} y={b2,b3,...,bk} 满足 sum < digit_sum - a 1 a_1 a1 的方案数。
示例程序
class Solution {
public:const int mod = 1e9 + 7;int dp[50][450];int dg(vector<int> v,int now,int sum,bool ok){if(sum < 0) return 0;if(now == v.size()){if(sum >= 0) return 1;return 0;}if(ok && dp[v.size() - now][sum]) return dp[v.size() - now][sum];if(ok){for(int i = 0; i <= 9; i++){dp[v.size() - now][sum] += dg(v,now + 1,sum - i,1);dp[v.size() - now][sum] %= mod;}return dp[v.size() - now][sum];}else{int ans = 0;for(int i = 0; i < v[now]; i++){// cout << now << " " << i << " " << sum << endl;ans += dg(v,now + 1,sum - i,1);ans %= mod;}ans += dg(v,now + 1,sum - v[now],0);ans %= mod;return ans;}}int count(string num1, string num2, int min_sum, int max_sum) {vector<int>v1,v2;for(int i = 0; i < num1.length(); i++){v1.push_back(num1[i] - '0');}for(int i = num1.length() - 1; i >= 0; i--){if(v1[i] - 1 >= 0){v1[i] -= 1;break;}else{v1[i] = 9;}}for(int i = 0; i < num2.length(); i++){v2.push_back(num2[i] - '0');}//cout << dg(v2,0,min_sum - 1,0) << endl;//cout << dg(v1,0,max_sum,0) << " " << dg(v1,0,min_sum - 1,0) << endl;return 1ll * ((dg(v2,0,max_sum,0) - dg(v2,0,min_sum - 1,0) - (dg(v1,0,max_sum,0) - dg(v1,0,min_sum - 1,0))) % mod + mod) % mod;return 0;}
};