题解 | #生产口罩#

算法思想一：动态规划

解题思路：

状态定义： $dp[i][j]$ 表示i条生产线，j名员工每天产多少口罩。
状态初始化：所有状态值初始化为0。
状态转移：每增加一条生产线，当前增加的生产线有两种选择，一种是选择闲置，另一种是在对应策略数组选择一个最佳策略。如果选择闲置，则相较于之前没有变化，即 $dp[i][j]=dp[i-1][j]$ ;如果选择某种策略，则需要当前人手大于等于策略需要人手，如果满足，则从所有选择中挑出一种产能最高的，即 $dp[i][j]=Math.max(dp[i][j],dp[i-1][j-p.x]+p.y)$ 。

代码展示：

JAVA版本

import java.util.*;
/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param strategy Point类二维数组 策略
     * @return int整型
     */
    public int producemask (int n, int m, Point[][] strategy) {
        // write code here
        //定义dp数组,dp[i]表示i个人每天最多生产多少口罩
        int[][] dp = new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                //当前状态下可能不选取任何策略。
                dp[i][j] = dp[i-1][j];
                //枚举每一种策略，然后选取当前状态的最优解。
                for(Point p :strategy[i-1]){
                    if(j < p.x) continue;
                    // 动态转移方程
                    dp[i][j] = Math.max(dp[i-1][j-p.x]+p.y,dp[i][j]);
                }
            }
        }
        return dp[n][m];
    }
}

复杂度分析

时间复杂度 $O(m*n)$ ：总共三层循环，需要执行 $m*n*strategy[i].size$ 次， $strategy[i].size$ 是一个常数，所以时间复杂度是 $O(m*n)$

空间复杂度 $O(m*n)$ ：需要额外大小为m*n的dp数组，所以空间复杂度为 $O(m*n)$ 。

算法思想二：动态规划优化

解题思路：

在基于方法一的思路上发现对于增加的生产线，当前总共生产的口罩数只和未增加这条生产线时的状态有关，并且当前状态的计算只与前面的状态有关，所以只需要从后往前遍历，按照上述的思路即可得到本题的答案。

图解：

代码展示：

JAVA版本

import java.util.*;
/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param strategy Point类二维数组 策略
     * @return int整型
     */
    public int producemask (int n, int m, Point[][] strategy) {
        //定义dp数组,dp[i]表示i个人每天最多生产多少口罩
        int[] dp=new int[m+1];
        for(int i=1;i<=n;i++){
            //从前往后，之前算过的状态会叠加，所以倒序访问
            for(int j=m;j>=1;j--){
                //枚举当前生产线的所有策略
                for(Point s:strategy[i-1]){
                    //如果当前人数大于策略分配人数，则比较哪个策略最优
                    if(j>=s.x){
                        dp[j]=Math.max(dp[j],dp[j-s.x]+s.y);
                    }
                }
            }
        }
        return dp[m];
    }
}

Python版本（会超时）

class Solution:
    def producemask(self , n , m , strategy ):
        # write code here
        # 定义dp数组,dp[i]表示i个人每天最多生产多少口罩
        dp=[0 for i in range(m+1)]
        for line in range(n):
            # 从前往后，之前算过的状态会叠加，所以倒序访问
            for person in range(m,0,-1):
                # 枚举当前生产线的所有策略
                for s in strategy[line]:
                    # 如果当前人数大于策略分配人数，则比较哪个策略最优
                    if s.x <= person:
                        # 状态转移方程
                        dp[person]=max(dp[person],s.y+dp[person-s.x])
        return dp[-1]

复杂度分析

时间复杂度 $O(m*n)$ ：总共三层循环，需要执行mnstrategy[i].size次，strategy[i].size是一个常数，所以时间复杂度是 $O(m*n)$

空间复杂度 $O(m)$ ：需要额外大小为m+1的dp数组，所以空间复杂度为 $O(m)$ 。