小行星采矿动态规划问题：求挖掘n克矿物的最小天数

要解决这个问题，我们可以用状态压缩的动态规划，核心是追踪每天结束时的机器人数量与对应开采的矿物量，通过迭代找到能开采至少n克矿物的最小天数。

状态定义 #

用字典存储每天的状态：robots的键是机器人数量，值是对应数量的机器人在当前天数结束时已开采的最大矿物量。对于相同数量的机器人，开采量越多越有利于后续完成任务，因此只保留最大开采量即可。

递推逻辑 #

每天的状态可以通过两种操作得到下一天的状态：

1. 全部开采：机器人数量不变，开采量增加当前机器人总数（每个机器人开采1克）。
2. 全部克隆：机器人数量翻倍（每个机器人都克隆自身），开采量不变（克隆不产生矿物）。

无需考虑部分克隆、部分开采的混合操作——因为混合操作的最优结果可以通过连续的全采或全克隆步骤等价实现，且仅保留全采/全克隆的状态已经足够覆盖所有可能的最优解，同时能大幅减少状态数量，提升效率。

终止条件 #

在每天迭代前，检查当前状态：

• 如果已有开采量≥n，直接返回当前天数。
• 如果当前开采量加上一天的最大开采量（即当前机器人数量）≥n，返回当前天数+1（再开采一天即可完成）。

代码实现 #

def min_mining_days(n):
    if n == 0:
        return 0
    # 初始状态：第0天，1个机器人，0克矿物
    day = 0
    robots = {1: 0}
    
    while True:
        # 检查是否能在当前或下一天完成任务
        for robot_count, mined in robots.items():
            if mined >= n:
                return day
            if mined + robot_count >= n:
                return day + 1
        
        # 生成下一天的状态
        next_robots = {}
        for r, m in robots.items():
            # 操作1：全部开采
            if r in next_robots:
                if m + r > next_robots[r]:
                    next_robots[r] = m + r
            else:
                next_robots[r] = m + r
            
            # 操作2：全部克隆
            new_r = 2 * r
            if new_r in next_robots:
                if m > next_robots[new_r]:
                    next_robots[new_r] = m
            else:
                next_robots[new_r] = m
        
        robots = next_robots
        day += 1

复杂度分析 #

• 时间复杂度：O(log n)，机器人数量最多每天翻倍，达到n级别的机器人数量仅需约20天（对于n=1e6），每天的状态数量也非常有限。
• 空间复杂度：O(log n)，每天的机器人数量最多是前一天的两倍，状态数量随天数呈对数增长。

内容的提问来源于stack exchange，提问作者PK96