MarsCode算法题之二分数字组合

这道题我觉得有困难的地方就是如何确定递推公式那一部分，需要一点思考。

2301_79318558

1637人浏览 · 2024-11-01 14:40:27

2301_79318558 · 2024-11-01 14:40:27 发布

1.问题描述

给定一个数组，请你把数组里的数字分为两组，使一组数字和的个位数等于 A（1 ≤ A ≤ 9），且剩余数字和的个位数等于 B（1 ≤ B ≤ 9）；或者一组数字的个数为零，但剩余数字和的个位数等于 A 或 B。请问一共有多少种划分方式？

示例1

输入:

3 1 2

1 1 1

输出:

3

示例2

输入:

3 3 5

1 1 1

输出:

1

难度等级

简单

题目链接

二分数组组合

2.解题思路

这道题让我们求组合数，即可以将数字分成两组，也可以把数字全部放到一组，剩下一组不放数字。第一种情况我们并不知道他是哪个数字放哪个组，要我们求组合数，我们可以用动态规划来解决；第二种情况，我们直接把所有数字累加之后取个位数，看它是否等于A或者等于B即可。

我们来详细讲一下，第一部分如何使用动态规划。我们要用动态规划来解题，首先第一个是先确定好dp数组的含义。这里，我们有三个变量，数的多少，第一组的个位数，第二组的个位数，所以我们要定义一个三维的数组dp[i][j][k]，dp[i][j][k]表示前i个数字，第一组的个位数为j，第二组的个位数为k时的划分方案数，dp[n][A][B]就是我们要求的答案。

         //dp: dp[i][j][k] 表示前i个数字，表示前i个数字，个位数分别为j和k时的划分方案数
        int[][][] dp = new int[n+1][10][10];

确定好dp数组的含义之后，我们接下来要来确定dp数组的递推公式。这里分为两种情况。

第一种情况是第i个数放到第一组中，递推公式是dp[i][j][k] += dp[i-1][((j+10) - array_a[i-1] %10) %10][k]。我来解释一下，因为我们当前的情况是基于第(i-1)个数的情况进行计算的，把第一个数放到第一组中，第二组的个位数不变，还是k，只有第一组的个位数可能改变了。我们假设再加array_a[i-1]之前的个位数是x，第一组的个位数 j 是 x 加上array_a[i-1]的个位数(array_a[i-1] % 10)之后的取个位数的结果。也就是 j = (x +array_a[i-1] % 10) % 10。所以dp[i][j][k]的情况会包括dp[i-1][x][k]所有可能发生的情况，所以要累加上 dp[i-1][x][k]，我们根据 j = (x +array_a[i-1] % 10) % 10 反解出x即可。我们移个项，得到x = j - array_a[i-1] % 10，因为个位数x必须为正数，j 可能比 array_a[i-1] % 10小，所以我们要给j 加上 10 ，然后再对结果取模来保证个位数为正数。

第二种情况是第i个数放到第二组中，递推公式是dp[i][j][k] = dp[i-1][j][((k + 10) - array_a[i-1] % 10) % 10]。原理和第一种情况一样，只是换了个位置而已，我就不多解释了。

                    //加入第一组
                    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];

确定完递推公式之后，我们就要根据递推公式来初始化dp数组，我们可以发现，dp数组总是在累加第(i-1)个数的情况，所以我们不能发现，我们要初始化的就是第0个数的情况。第0个数，那没得说，无论是哪一组，都没有数，个位都是0，只有这一种情况，所以dp数组的初始化就是dp[0][0][0] = 1。可能有人会问，为什么不是初始化为0，因为我们的递推公式是累加的，如果初始化为0，那么无论怎么累加，结果都是0，所以我们不能初始化为0。

        //初始化dp数组
        dp[0][0][0] = 1;
        int sum = 0;

初始化完dp数组之后，我们就可以正常的遍历了，三个for循环，第一个表示第i个数，第二个表示第一组的个位数，第二个表示第二组的个位数，用递推公式进行计算即可。

        //第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];

        }

遍历完成之后,dp[n][A][B]就是我们要的结果了，但是不用忘了这只是两种组合方式种的一种，我们还要将另一种所有数都放在一组的情况加上才是我们的最终结果。

        //总和个位数是否为A
        int a = sum  % 10 == A? 1:0;
        //总和个位数是否为B
        int b = sum  % 10 == B? 1:0;
        int result = dp[n][A][B] + a + b;
        return result;

3.代码展示

public class Main {
    public static int solution(int n, int A, int B, int[] array_a) {
        //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];

        }
        //总和个位数是否为A
        int a = sum  % 10 == A? 1:0;
        //总和个位数是否为B
        int b = sum  % 10 == B? 1:0;
        int result = dp[n][A][B] + a + b;
        return result;
    }

    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);
    }
}