查建设施工资质的网站,网站怎么做桌面快速链接,wordpress本地化,城市建设协会网站1.0.理论基础
动态规划主要解决的问题种类有#xff1a;
背包问题打家劫舍股票问题子序列问题
解决步骤#xff1a;
dp数组及其下标的意义递推公式dp数组初始化遍历顺序打印dp数组
2.0.相关力扣题
509.斐波那契数列
class Solution:def fib(self, n: int) - int:i…1.0.理论基础
动态规划主要解决的问题种类有
背包问题打家劫舍股票问题子序列问题
解决步骤
dp数组及其下标的意义递推公式dp数组初始化遍历顺序打印dp数组
2.0.相关力扣题
509.斐波那契数列
class Solution:def fib(self, n: int) - int:if n0:return 0if n1:return 1dp [0]*35dp[1] 1for i in range(2,31):dp[i] dp[i-1]dp[i-2]return dp[n]效率0ms击败100.00%
状态压缩
再优化一下因为每个斐波那契数只和它相邻的两个数有关所以我们其实不需要存储三十多个长度只需要保留2个数的信息即可。也就是状态压缩。
class Solution:def fib(self, n: int) - int:if n0:return 0if n1:return 1dp [0]*2dp[1]1sum 0for i in range(2,n):sum dp[0]dp[1]dp[0] dp[1]dp[1] sumreturn dp[0]dp[1]70.爬楼梯
跟509.斐波那契数列很像
class Solution:def climbStairs(self, n: int) - int:if n1:return 1if n2:return 2dp [0] * 50dp[1] 1dp[2] 2for i in range(3,n1):dp[i] dp[i-1]dp[i-2]print(dp)return dp[n]
效率0ms击败100.00%
状态压缩
class Solution:def climbStairs(self, n: int) - int:if n1:return 1if n2:return 2dp [0] * 4dp[1] 1dp[2] 2sum 0for i in range(3,n):sum dp[1]dp[2]dp[1] dp[2]dp[2] sumreturn dp[1]dp[2]756.使用最小代价爬楼梯
需要注意的是这里的dp[i]代表着爬到台阶为i时所需的最小代价。
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost)if n 2:return min(cost[0],cost[1])dp [0]*1005dp[0] 0dp[1] 0for i in range(2,n1):dp[i] min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])return dp[n]效率2ms击败83.69%
