数位动态规划（Digit Dynamic Programming，数位DP）是一种动态规划算法，用于解决涉及数字各位数的组合问题。以下是一个数位DP的Java代码示例，用于计算在区间 [1, N] 内，所有数字的各位之和等于给定值 K 的个数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public class DigitDP {
public static int countNumbersWithDigitSum(int N, int K) {
int[][] dp = new int[N + 1][K + 1];
int MOD = (int) 1e9 + 7;
dp[0][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= K; j++) {
for (int d = 0; d <= 9; d++) {
if (j >= d) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - d]) % MOD;
}
}
}
}
int result = 0;
for (int d = 1; d <= 9; d++) {
if (K >= d) {
result = (result + dp[N][K - d]) % MOD;
}
}
return result;
}
public static void main(String[] args) {
int N = 2;
int K = 2;
int count = countNumbersWithDigitSum(N, K);
System.out.println("Count of numbers with digit sum " + K + " in range [1, " + N + "]: " + count);
}
}
|
在这个示例中，countNumbersWithDigitSum 方法使用数位DP解决了计算各个数字各位数之和等于给定值 K 的数字个数问题。算法通过构建一个二维数组 dp 来保存状态转移，从而计算符合条件的数字个数。
这个示例是一个数位DP的实现，实际应用中可能需要根据不同的问题进行适当的修改。