代码随想录算法训练营day48 | 70. 爬楼梯 （进阶）、322. 零钱兑换、279.完全平方数

70. 爬楼梯 （进阶）

本题和377. 组合总和 Ⅳ一样。求的是排列，因此背包重量为外层循环，物品为内层循环。

def climbing_stairs(n,m):
    dp = [0]*(n+1) # 背包总容量
    dp[0] = 1 
    # 排列题，注意循环顺序，背包在外物品在内
    for j in range(1,n+1):
        for i in range(1,m+1):
            if j>=i:
                dp[j] += dp[j-i] # 这里i就是重量而非index
    return dp[n]

if __name__ == '__main__':
    n,m = list(map(int,input().split(' ')))
    print(climbing_stairs(n,m))

322. 零钱兑换

1. 确认dp数组以及下标的含义：凑成总金额j所需要的最少硬币个数为dp[j]
2. 确认递推公式：dp[j] = min(dp[j], dp[j-coins[i]]+1)
3. dp数组的初始化：因为求最小值，因此初始化为最大值，遍历中可被覆盖。dp[0] = 0
4. 确认遍历顺序：因为求的是最少个数，和排列组合没有关系，因此物品和背包重量内外层顺序无所谓
5. 举例推导dp数组

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin, amount+1):
                dp[j] = min(dp[j], dp[j-coin] + 1)
        if dp[amount] == float('inf'):
            return -1
        else:
            return dp[amount]

279.完全平方数

完全背包

1. 确认dp数组以及下标的含义：组成和为j的完全平方数的最少数量为dp[j]
2. 确认递推公式：dp[j] = min(dp[j], dp[j-weight[i]] + 1)
3. dp数组的初始化：求最小值，则初始化为最大值。dp[0] = 0
4. 确认遍历顺序：求最小值，内外层顺序没有要求。背包重量正序遍历
5. 举例推导dp数组

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, int(math.sqrt(n))+1):
            num = i * i
            for j in range(num, n+1):
                dp[j] = min(dp[j], dp[j-num] + 1)
        return dp[n]

平方根可以使用下面的写法

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        for i in range(1, int(n ** 0.5) + 1):  # 遍历物品
            for j in range(i * i, n + 1):  # 遍历背包
                # 更新凑成数字 j 所需的最少完全平方数数量
                dp[j] = min(dp[j - i * i] + 1, dp[j])

        return dp[n]