算法题——华为OD机试——整数划分排序/员工分月饼——动态规划——Java

简介

一个考察动态规划的机试题的数学模型建立，和两种思路的取舍

题目

公司分月饼，m个员工，买了n个月饼，m <= n，每个员工至少分一个月饼，但是也可以分到多个，单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2。

但需要满足Max1-Max2 <= 3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n), 想要满足Max(n-1) - Max(n) <= 3，问有多少种分月饼的方法？

输入描述：

每一行输入m，n，表示m个员工，n个月饼，m <=n

输出描述：

输出有多少种分法

示例1：

输入

2 4

输出

2

说明

4=1+3

4=2+2

注意：1+3和3+1要算成同一种分法

示例2：

输入

3 5

输出

2

说明

5=1+1+3

5=1+2+3

示例3：

输入

3 12

输出

6

说明

满足要求的6种分法：

1、12 = 1 + 1 + 10 （Max1=10， Max2=1，不满足Max1-Max2 <= 3的约束）

2、12 = 1 + 2 + 9 （Max1=9，Max2=2，不满足Max1-Max2 <= 3的约束）

3、12 = 1 + 3 + 8 （Max1=8，Max2=3，不满足Max1-Max2 <= 3的约束）

4、12 = 1 + 4 + 7 （Max1=7，Max2=4，Max3=1， 满足要求）

5、12 = 1 + 5 + 6 （Max1=6，Max2=5，Max3=1， 不满足要求）

6、12 = 2 + 2 + 8 （Max1=8，Max2=2，不满足要求）

7、12 = 2 + 3 + 7 （Max1=7，Max2=3，不满足要求）

8、12 = 2 + 4 + 6 （Max1=6，Max2=4，Max3=2， 满足要求）

9、12 = 2 + 5 + 5 （Max1=5，Max2=2 满足要求）

10、12 = 3 + 3 + 6 （Max1=6，Max2=3 满足要求）

11、12 = 3 + 4 + 5 （Max1=5，Max2=4，Max3=3 满足要求）

12 = 4 + 4 + 4 （Max1=4，满足要求）

平台场景

牛客网 可以选择使用多种语言 我选择Java写的

大多数题目需要做输入输出训练

但是这题不用 给定了 形参 m员工 n月饼 最后return方案数量即可

数学模型

把正整数n分为m份自然数，m <= n，排序后，任意相邻数相差不超过3

方案1-动态规划

思路代码

* 这是动态规划方案
* 定义状态 dp[i][j][k] 表示前 i 个人分配了 j 个月饼，且第 i 个人分配了 k 个月饼的方案数。
* 状态方程为 dp[i][j]=∑k=1>>3​ dp[i−1][j−k]
* 时空复杂度都是 m*n*n*n

    public static int countWays(int m, int n) {
        int[][][] dp = new int[m + 1][n + 1][n + 1];
        // 初始化
        for (int k = 1; k <= n ; k++) {
            dp[1][k][k] = 1; // 只有1个员工时，只有一种分法
        }
        // 动态规划
        for (int i = 1; i <= m; i++) {
            for (int j = i; j <= n; j++) { // 确保月饼数量不少于员工数
                for (int k = 1; k <= j; k++) { // 每个员工至少分得1个月饼
                    for (int l = 1; l <= k; l++) { // 确保当前分配不超过上一个员工的分配
                        dp[i][j][k] += dp[i - 1][j - k][l];
                    }
                }
            }
        }
 
        // 汇总结果
        int count = 0;
        for (int k = 0; k <= n; k++) {
            System.out.println("dp" + m + n + k + "  " + dp[m][n][k]);
            count += dp[m][n][k];
        }
 
        return count;
    }

评价总结

* 对特定问题（方案数量而不是具体方案）是简单了，但实际上压缩损失了很多信息
* 对方案数量的计算涉及到是否去重（可以通过 具体分配的是否递增来表达）
* 对于有需求变化的场景会加大开发难度

方案2

思路代码

* 这是递归方案，遍历所有树枝
* 输出所有方案具体划分内容
* 时间复杂度 n^m 空间复杂度 m+结果数量

    private static List<List<Integer>> partition(int n, int m) {
        List<List<Integer>> result = new ArrayList<>();
        partitionHelper(n, m, 0, new ArrayList<>(), result);
        return result;
    }
 
    private static void partitionHelper(int n, int m, int last, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == m) {
            if (n == 0) {
                result.add(new ArrayList<>(current));
            }
            return;
        }
 
        int start = current.isEmpty() ? 1 : Math.max(current.get(current.size() - 1), 1);
        int end = current.isEmpty() ? n/m : Math.min(n, last + 3);
        for (int i = start; i <= end; i++) {
            current.add(i);
            partitionHelper(n - i, m, i, current, result);
            current.remove(current.size() - 1);
        }
    }
 
 
 
    public static void test() {
        List<List<Integer>> result = partition(4, 2);
 
        System.out.println(result.size());
        for (List<Integer> partition : result) {
            System.out.println(partition);
        }
    }

评价

不是最切合题意的高效方式，但是符合问题生长方向

过程可控，最后打印所有的方案内容