C# 记忆化搜索代码
public class Solution {
private int mod = 1000000007;
public int Count(string num1, string num2, int min_sum, int max_sum) {
int sum = 0;
foreach (char c in num1){
sum += c - '0';
}
// 将问题转化为0~num2的数目减去0~num1的数目, 特判num1的数位和是否在要求范围内
return (DP(num2) - DP(num1) + ((sum >= min_sum && sum <= max_sum) ? 1 : 0) + mod) % mod;
int DP(string num){
int n = num.Length;
int[][][] cache = new int[n][][];
for (int i = 0; i < n; i++){
int min = Math.Min(n * 9, max_sum);
cache[i] = new int[min + 1][];
for (int j = 0; j <= min; j++){
cache[i][j] = new int[2];
Array.Fill(cache[i][j], -1);
}
}
return DFS(0, 0, 1);
// 满足前i位数位和为s的整数数目, limit表示当前位是否有最大值限制
int DFS(int i, int s, int limit){
if (s > max_sum) return 0;
if (i == n) return s >= min_sum ? 1 : 0;
if (cache[i][s][limit] != -1) return cache[i][s][limit];
int max = limit == 1 ? num[i] - '0' : 9;
cache[i][s][limit] = 0;
for (int j = 0; j <= max; j++){
int t = (limit == 1 && j == max) ? 1 : 0;
cache[i][s][limit] = (cache[i][s][limit] + DFS(i + 1, s + j, t)) % mod;
}
return cache[i][s][limit];
}
}
}
}
C# 空间优化代码
public class Solution {
private int mod = 1000000007;
public int Count(string num1, string num2, int min_sum, int max_sum) {
int sum = 0;
foreach (char c in num1){
sum += c - '0';
}
return (DP(num2) - DP(num1) + ((sum >= min_sum && sum <= max_sum) ? 1 : 0) + mod) % mod;
int DP(string num){
int n = num.Length;
int[][] cache = new int[n][];
for (int i = 0; i < n; i++){
int min = Math.Min(n * 9, max_sum);
cache[i] = new int[min + 1];
Array.Fill(cache[i], -1);
}
return DFS(0, 0, 1);
int DFS(int i, int s, int limit){
if (s > max_sum) return 0;
if (i == n) return s >= min_sum ? 1 : 0;
if (limit == 0 && cache[i][s] != -1) return cache[i][s];
int max = limit == 1 ? num[i] - '0' : 9;
cache[i][s] = 0;
for (int j = 0; j <= max; j++){
int t = (limit == 1 && j == max) ? 1 : 0;
cache[i][s] = (cache[i][s] + DFS(i + 1, s + j, t)) % mod;
}
return cache[i][s];
}
}
}
}