代码随想录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]