如何用动态规划表解决最小不可构造找零问题？

问题描述 #

给定一个由正整数组成的数组（代表持有的硬币面值，数组可包含重复元素），编写函数返回无法用这些硬币构造的最小找零金额。例如输入数组为[1, 2, 5]时，无法构造的最小找零金额是4，因为我们可以构造1、2、3（1+2）和5。

已知最优解法 #

def nonConstructibleChange(coins):
    coins.sort()
    minimum_change = 0
    for coin in coins:
        if coin > minimum_change + 1:
            break
        minimum_change += coin
    return minimum_change + 1

动态规划表实现思路与未完成代码 #

希望用基于矩阵的暴力解法实现，设定矩阵的行代表硬币，列代表1到硬币总和的数值范围，以下是未完成的代码：

def nonConstructibleChange(coins):
    coins = sorted(coins)
    if 1 not in coins:
        return 1
    if len(coins)==1:
        return 2
    sum_coins = sum(coins)

    array = [[0 for val in range(sum_coins)] for val in range(len(coins))]
    array[0][0]=1

    for val in range(len(coins)):
        coin = coins[val]
        for valtwo in range(sum_coins):
            if coin==valtwo+1:
                array[val][valtwo]=1
            else:
                if val!=0 and valtwo!=0 and valtwo<=val:
                    if array[val-1][valtwo-1]!=1 and array[val][valtwo-1]!=1 and array[val-1][valtwo]!=1:
                        return val-1
                    else:
                        array[val][valtwo]=1

动态规划表解法完成指导 #

核心逻辑梳理 #

动态规划表的核心是记录使用前i个硬币能否构造出金额j，建议调整索引含义让逻辑更清晰：让矩阵dp[i][j]代表使用前i+1个硬币（行从0开始计数）能否构造出金额j，列范围覆盖0到硬币总和（金额0表示不选任何硬币，必然可构造）。

步骤修正与代码完善 #

1. 矩阵初始化：

   • 所有行的第0列（对应金额0）设为1，因为不选任何硬币就能构造金额0。
   • 第一行（仅使用第一个硬币）：只有金额等于该硬币面值的位置设为1，其余为0。

2. 状态转移填充矩阵：
   遍历每个硬币和每个金额：

   • 如果当前硬币面值大于目标金额j：能否构造j完全取决于前i个硬币的结果，即dp[i][j] = dp[i-1][j]。
   • 如果当前硬币面值小于等于目标金额j：有两种选择——不用当前硬币（继承dp[i-1][j]），或用当前硬币（检查dp[i-1][j - 当前硬币面值]是否为1），只要其中一种可行，dp[i][j]就设为1。

3. 查找结果：
   从金额1开始遍历到硬币总和，找到第一个dp[-1][j]为0的金额就是答案；如果所有金额都能构造，返回总和+1。

完整代码实现 #

def nonConstructibleChange(coins):
    coins = sorted(coins)
    
    # 特殊情况：没有1的话，最小无法构造的就是1
    if 1 not in coins:
        return 1
    
    sum_coins = sum(coins)
    n = len(coins)
    
    # dp[i][j]：使用前i+1个硬币能否构造金额j
    dp = [[0] * (sum_coins + 1) for _ in range(n)]
    
    # 初始化：金额0总是可以构造
    for i in range(n):
        dp[i][0] = 1
    
    # 初始化第一行（仅使用第一个硬币）
    first_coin = coins[0]
    if first_coin <= sum_coins:
        dp[0][first_coin] = 1
    
    # 填充动态规划表
    for i in range(1, n):
        current_coin = coins[i]
        for j in range(1, sum_coins + 1):
            # 情况1：不使用当前硬币，继承上一行的结果
            dp[i][j] = dp[i-1][j]
            # 情况2：使用当前硬币，如果金额足够且剩余金额可构造
            if j >= current_coin:
                if dp[i-1][j - current_coin] == 1:
                    dp[i][j] = 1
    
    # 查找最小无法构造的金额
    for j in range(1, sum_coins + 1):
        if dp[-1][j] == 0:
            return j
    
    # 所有金额都能构造，返回总和+1
    return sum_coins + 1

验证示例 #

• 输入[1,2,5]：矩阵中金额4对应的dp[-1][4]为0，返回4，符合预期。
• 输入[1,1,3]：所有1-5的金额都能构造，返回6。

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