MarsCode青训营序章Day2|稀土掘金-32.二分数字组合

稀土掘金-32.二分数字组合（32.二分数字组合）

这道题笔者也没有正确作对，参考的是这位老哥的思路：MarsCode算法题之二分数字组合-CSDN博客

顺便吐槽一下MarsCode对于简单题的“定义”，在这里你既能看到让人直呼“转人工”难度的题目，也能看到让人直呼“我是人机”难度的题目！

题目分析：

给定一个数组nums，对其进行二分分组，使得两个分组的数字和的个位数分别等于A和B，允许一个分组为空时另一个分组为原数组nums的情况，求这样的分组有多少个。

解题思路：

本题求取组合数，除一个分组为空，另一个分组为原数组的情况外，其余的普通情况，我们考虑使用动态规划解决。

首先定义dp数组如下：

对dp[i][j][k]，表示前i个数字，第一个分组的数字和个位数为j，第二个分组的数字和个位数为k，这样的分组情况的方案数即为dp[i][j][k]。

因而，最终我们所需的，就是dp[n][A][B]。

int[][][] dp = new int[n+1][10][10];

然后确定dp数组的递推公式：

1. 将第i个数放入第一个分组时时，是基于前i-1个数的分组方式进行计算的。

1. 1. 将第i个数放到第一个分组中，则第二个分组的数字和个位数仍未k
   2. 假设加上第i个数（array_a[i-1]）之前第一个分组的个位数是x
   3. 则j = (x + array_a[i-1] %10) %10
   4. 由于dp[i][j][k]必然包含dp[i-1][x][k]所有可能发生的情况，所以必须累加上dp[i-1][x][k]
   5. 反解j关于x的表达式可得：x = j - array_a[i-1] % 10
   6. 为确保x为正，则x = ((j+10) - array_a[i-1] % 10) %10
   7. 最终可得 dp[i][j][k] = dp[i-1][((j+10) - array_a[i-1] % 10) %10][k]

1. 同理可得：将第i个数放到第二个分组中时：

1. 1. dp[i][j][k] = dp[i-1][j][((k+10) - array_a[i-1] % 10) %10]

接着，根据递推公式，初始化dp数组

可以发现：dp数组总是在累加第i-1个数的情况

故我们需要初始化的就是第0个数的情况

由dp数组定义，第0个数的情况就是分组中尚没有加入任何数的情况，故数字和的个位数都是0，且这种情况是唯一的。

最终得到dp数组的初始化为：dp[0][0][0] = 1;

另外，在过程中累加n个数的和

求取n个数的和sum，用于遍历完全后，求取“一个分组为空，另一个分组为原数组”的特殊情况。

最终代码如下：

注意：为什么仅取dp[n][A][B]而不累加dp[n][B][A]？因为分组的序号是我们人为标注的，第一个分组与第二个分组并无顺序关系，计算过程中也可以看到，对于每一个dp[i][j][k]，均考虑了第i个数即array_a[i-1]被加到第一组或第二组时的累加情况。所以，此处取dp[n][B][A]或dp[n][A][B]是没有差别的，可不要重复啦。

public class Main {
    public static int solution(int n, int A, int B, int[] array_a) {
        // write code here
        //dp: dp[i][j][k] 表示前i个数字，二分分组的数字和的个位数分别为j和k时的划分方案数
        int[][][] dp = new int[n+1][10][10];
        //初始化dp数组
        dp[0][0][0] = 1;
        int sum = 0;
        //第i个数
        for(int i = 1;i <= array_a.length;i++){
            //第一组的数字和的个位数
            for(int j = 0;j < 10;j++){
                //第二组的数字和的个位数
                for(int k = 0;k < 10;k++){
                    //加入第一组
                    dp[i][j][k] += dp[i-1][((j + 10) - array_a[i-1] % 10) % 10][k];
                    //加入第二组
                    dp[i][j][k] += dp[i-1][j][((k + 10) - array_a[i-1] % 10) % 10];
                }
            }
            //累加
            sum += array_a[i-1];
        }
        int situationCount = dp[n][A][B];
        //总和个位数是否为A
        if(sum == A) situationCount++;
        //总和个位数是否为B
        if(sum == B) situationCount++;
        return situationCount;
    }
 
    public static void main(String[] args) {
        //  You can add more test cases here
        int[] array1 = {1, 1, 1};
        int[] array2 = {1, 1, 1};
        int[] array3 = {1, 1};
 
        System.out.println(solution(3, 1, 2, array1) == 3);
        System.out.println(solution(3, 3, 5, array2) == 1);
        System.out.println(solution(2, 1, 1, array3) == 2);
    }
}