代码随想录11:动态规划

BBigSun 评论313阅读模式

代码随想录11:动态规划

什么是动态规划?

动态规划,英文名称:Dynamic Programming,简称DP。文章源自十年又十年-https://www.bbigsun.com/418.html

如果某一问题有很多重叠子问题,使用动态规划是最有效的。文章源自十年又十年-https://www.bbigsun.com/418.html

动态规划中的每一个状态一定由上一个状态推导而出,这一点区别于贪心,贪心没有状态推导,而是从局部直接选出最优。文章源自十年又十年-https://www.bbigsun.com/418.html

举例:有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是 value[i]。每件物品只能使用一次,求解将哪些物品装入背包总价值最大。文章源自十年又十年-https://www.bbigsun.com/418.html

dp[j] 代表总价值,dp[j] = max(dp[j], dp[j-weight[i]] + value[i])文章源自十年又十年-https://www.bbigsun.com/418.html

动态规划的解题步骤

  • (1)确定 dp 数组以及下标含义
  • (2)确定递推公式
  • (3)dp 数组如何初始化
  • (4)确定遍历顺序
  • (5)举例推导 dp 数组

通过打印 dp 数组进行 debug文章源自十年又十年-https://www.bbigsun.com/418.html

斐波那契数列

f(n) = f(n-1) + f(n-2) , f(0) = 0, f(1) = 1文章源自十年又十年-https://www.bbigsun.com/418.html

思路:文章源自十年又十年-https://www.bbigsun.com/418.html

  • dp[i] 斐波那契数列的值
  • 递推公式:dp[i] = dp[i-1] + dp[i-2]
  • 初始化:dp[0] = 0, dp[1] = 1, dp[2] = 1
  • 遍历顺序:从前往后
def solution(n):
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, len(n)+1)
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
文章源自十年又十年-https://www.bbigsun.com/418.html文章源自十年又十年-https://www.bbigsun.com/418.html

纸上得来终觉浅,绝知此事要躬行。

weinxin
17688689121
我的微信
微信扫一扫
BBigSun
  • 本文由 BBigSun 发表于 2023年 3月 31日 08:31:28
  • 转载请务必保留本文链接:https://www.bbigsun.com/418.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定