70. 爬楼梯
题目简述:
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
思路:
1. 要想爬到第n阶,必须先上第n-1阶或者n-2阶
2. 利用动态规划,定义初始条件dp[0]=1,dp[1]=2
3. 有dp[i]=dp[i-1]+dp[i-2],其中i>=2
代码如下:
class Solution: def climbStairs(self, n: int) -> int: if n==1: return 1 if n==2: return 2 dp=[1,1] for i in range(2,n+1): dp.append(dp[i-1]+dp[i-2]) return dp[n]
322. 零钱兑换
题目简述:
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
思路:
1. dp[x]表示组成总金额x所需的最少的硬币个数,初始化为inf,并令dp[0]=0
2. 则dp[x]=min(dp[x-coin1],dp[x-coin2]......)+1,其中coin1,coin2等都是coins数组里面的值
3. 先遍历coin,在令x从coin遍历到amount,不断更新dp[x]
4. 最后判断dp[amount]是否合法,是否为正常值,不是inf
代码如下:
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: for x in range(coin, amount + 1): dp[x] = min(dp[x], dp[x - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1
279. 完全平方数
题目简述:
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
思路:
1. 动态规划
2. 创建nums数组,里面存有1至小于根号n的最大正整数之间的数的平方值
3. 仿照前面几题,不断更新动态规划数组
代码如下:
class Solution: def numSquares(self, n: int) -> int: nums = [i*i for i in range(1, int(n**0.5)+1)] f = [0] + [float('inf')]*n for num in nums: for j in range(num, n+1): f[j] = min(f[j], f[j-num]+1) return f[-1]
标签:return,int,322,amount,279,day45,coin,inf,dp From: https://www.cnblogs.com/cp1999/p/17413049.html