代码随想录｜Day42｜动态规划 part07｜● 70. 爬楼梯 （进阶）● 322. 零钱兑换 ● 279.完全平方数

本文主要是介绍代码随想录｜Day42｜动态规划 part07｜● 70. 爬楼梯 （进阶）● 322. 零钱兑换 ● 279.完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

70. 爬楼梯 （进阶）

 322. 零钱兑换

class Solution:

    def climbStairs(self, n: int) -> int:

        if n <= 1:

            return n

        dp = [0] * (n + 1)

        dp[0] = 0

        dp[1] = 1

        dp[2] = 2

        for i in range(3, n + 1):

            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

279.完全平方数 

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):

                dp[j] = min(dp[j], dp[j - i * i] + 1)

        return dp[n]

这篇关于代码随想录｜Day42｜动态规划 part07｜● 70. 爬楼梯 （进阶）● 322. 零钱兑换 ● 279.完全平方数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---