「程序员必须掌握的算法」动态规划「中篇」

「程序员必须掌握的算法」动态规划「中篇」

在程序员的日常工作中，掌握各种算法是必不可少的。其中动态规划是常用的一种算法，在解决优化问题方面有着广泛的应用。本文主要介绍动态规划的中等难度内容，包括二维DP和数位DP。

二维DP

二维动态规划（DP）是指，用一个二维数组来表示状态，其中第一维表示选取到哪个元素，第二维表示当前选取的状态。这种方法在解决问题中，需要转移的状态比较复杂的情况下特别有用。

例题1：矩阵路径计数

题目描述：给定一个 n × m n \times mn×m 的矩阵，从左上角走到右下角，一共有多少种走法。其中每次只能向右或向下走。

思路分析：定义状态 d p i , j dp_{i,j}dpi,j 表示从 ( 1 , 1 ) (1,1)(1,1) 走到 ( i , j ) (i,j)(i,j) 的方案数，那么状态转移方程就可以定义为：d p i , j = d p i − 1 , j + d p i , j − 1 dp_{i,j} = dp_{i-1,j} + dp_{i,j-1}dpi,j=dpi−1,j+dpi,j−1，其中 d p i − 1 , j dp_{i-1,j}dpi−1,j 表示从上面的位置走到 ( i , j ) (i,j)(i,j)，d p i , j − 1 dp_{i,j-1}dpi,j−1 表示从左边的位置走到 ( i , j ) (i,j)(i,j)，两种情况的方案数相加即可得到从 ( 1 , 1 ) (1,1)(1,1) 走到 ( i , j ) (i,j)(i,j) 的方案数。特别地，当 i = 1 i=1i=1 或 j = 1 j=1j=1 时，只有一条路径，因此 d p 1 , j = d p i , 1 = 1 dp_{1,j}=dp_{i,1}=1dp1,j=dpi,1=1。

最后，返回 d p n , m dp_{n,m}dpn,m 就是从左上角走到右下角的方案数。

int[][] dp = new int[n][m];
for (int i = 0; i < n; i++) {
    dp[i][0] = 1;
}
for (int i = 0; i < m; i++) {
    dp[0][i] = 1;
}
for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}
return dp[n-1][m-1];

数位DP

数位DP是指，用一个数字的各个位数作为状态，来解决数字相关问题的一种算法。数位DP的思路是把数字拆开，按照位数逐位处理，求解每一位的方案数，最后组合得到最终的结果。

例题2：数字和为 k kk 的数的个数

题目描述：给定两个正整数 a aa 和 b bb，求满足 a ≤ x ≤ b a \leq x \leq ba≤x≤b，并且 x xx 的所有数字之和等于 k kk 的自然数的个数。

思路分析：我们可以用数位DP的方法来解决这个问题。和前面的例题一样，我们定义状态 d p i , j , k dp_{i,j,k}dpi,j,k 表示当前处理到第 i ii 位，数字和为 j jj 的方案数。那么状态转移方程可以定义为：d p i , j , k = ∑ d = 0 9 d p i − 1 , j − d , k − 1 dp_{i,j,k} = \sum \limits _{d=0} ^9 dp_{i-1,j-d,k-1}dpi,j,k=d=0∑9dpi−1,j−d,k−1，其中 d dd 表示当前处理到的数字，也就是第 i ii 位的数字。那么 d p i − 1 , j − d , k − d dp_{i-1,j-d,k-d}dpi−1,j−d,k−d 就表示前 i − 1 i-1i−1 位数字和为 j − d j-dj−d，数字个数为 k − 1 k-1k−1 的方案数，然后把所有 d dd 的情况都累加到一起即可得到 d p i , j , k dp_{i,j,k}dpi,j,k 的值。特别地，当 i = 0 i=0i=0 且 j = k = 0 j=k=0j=k=0 时，可以将此视为一个合法方案，即 d p 0 , 0 , 0 = 1 dp_{0,0,0}=1dp0,0,0=1。

下面，我们对数位DP的状态进行优化，因为对于一个数字 n nn，它的各个数位的数字之和最大为 9 99，因此 d p i , j , k = 0 dp_{i,j,k}=0dpi,j,k=0 当 j > 9 k j>9kj>9k，即当前处理到第 i ii 位，数字和大于 9 k 9k9k 时可以直接跳过。另外，我们为了方便计算，可以将上限转化成字符串，比如将 b = 1234 b=1234b=1234 转化为 s = " 1234 " s="1234"s="1234"，然后逐位考虑，如果 s i < d s_i<dsi<d，那么当前数字不能取 d dd，下一位需要继续考虑，如果 s i = d s_i=dsi=d，那么当前数字可以取 d dd，下一位也需要继续考虑，如果 s i > d s_i>dsi>d，那么下一位可以任意填充数字，无需继续考虑。

在实现的时候，我们需要用一个 s u m sumsum 变量来记录当前数字的各个位数之和，把所有状态的方案数相加，得到最终的结果。

public int count(int n, int k) {
    int[][][] dp = new int[11][91][91];
    dp[0][0][0] = 1;
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j <= 81; j++) {
            for (int l = 0; l <= 81; l++) {
                for (int d = 0; d <= 9; d++) {
                    if (j >= d && l >= d) {
                        dp[i][j][l] += dp[i - 1][j - d][l - d];
                    }
                }
            }
        }
    }
    int ans = 0;
    String s = String.valueOf(n);
    int[] num = new int[s.length() + 1];
    for (int i = 0; i < s.length(); i++) {
        num[i + 1] = s.charAt(i) - '0';
    }
    for (int i = 1; i < num.length; i++) {
        for (int j = 0; j < num[i]; j++) {
            if (j <= k - ans - (num.length - i) * 9) {
                ans += dp[num.length - i][k - ans - j][(num.length - i) * 9 + j];
            }
        }
        if (num[i] > k - ans - (num.length - i) * 9) {
            break;
        }
        sum += num[i];
    }
    if (sum == k) {
        ans++;
    }
    return ans;
}

结语

本文主要介绍了动态规划的中等难度内容，包括二维DP和数位DP，并附有两道例题作为模版参考。通过实际运用和练习，相信读者可以更加深入地理解动态规划的思想和应用。