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

r囧r小猫 2023-10-15 21:12 56阅读 0赞

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

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

### 二维DP ###

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

#### 例题1：矩阵路径计数 ####

题目描述：给定一个  n × m n \\times m n×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=1 i=1 或  j = 1 j=1 j=1 时，只有一条路径，因此  d p 1 , j = d p i , 1 = 1 dp\_\{1,j\}=dp\_\{i,1\}=1 dp1,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 k k 的数的个数 ####

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

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

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

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

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，并附有两道例题作为模版参考。通过实际运用和练习，相信读者可以更加深入地理解动态规划的思想和应用。