动态规划理论基础

什么是动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，

常见类型

基础问题

背包问题

打家劫舍

股票问题

子序列问题

动规的误区

递推公式不是最主要的，仅仅是一部分

DP数组

DP数组究竟表示什么意思以及下标的含义

DP数组如何初始化

DP数组遍历顺序

打印DP数组（查错debug）

递归如何debug

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。

如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。

这也是我为什么在动规五步曲里强调推导dp数组的重要性。

举个例子哈：在「代码随想录」刷题小分队微信群里，一些录友可能代码通过不了，会把代码抛到讨论群里问：我这里代码都已经和题解一模一样了，为什么通过不了呢？

发出这样的问题之前，其实可以自己先思考这三个问题：

• 这道题目我举例推导状态转移公式了么？
• 我打印dp数组的日志了么？
• 打印出来了dp数组和我想的一样么？

如果这灵魂三问自己都做到了，基本上这道题目也就解决了，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。

然后在问问题，目的性就很强了，群里的小伙伴也可以快速知道提问者的疑惑了。

注意这里不是说不让大家问问题哈， 而是说问问题之前要有自己的思考，问题要问到点子上！

大家工作之后就会发现，特别是大厂，问问题是一个专业活，是的，问问题也要体现出专业！

如果问同事很不专业的问题，同事们会懒的回答，领导也会认为你缺乏思考能力，这对职场发展是很不利的。

所以大家在刷题的时候，就锻炼自己养成专业提问的好习惯。

递归五部曲总结

DP数组定义以及下标的含义

递推公式

DP数组如何初始化

DP数组遍历顺序

打印DP数组（查错debug）

509. 斐波那契数列

文档讲解：代码随想录

题目链接：. - 力扣（LeetCode）

dp数组

一维或者二维用来做状态转移的dp数组

dp[i]:第i个斐波那契的数组

递推公式

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

dp数组如何初始化

dp[0]=1，dp[1]=1

遍历顺序

从前向后遍历，从i=2开始遍历

debug

如果有问题就打印dp数组

class Solution:
    def fib(self, n: int) -> int:
        dp = [1]*(n+1) #因为有f(n)，所以数组长度是n+1
        dp[0]= 0
        for i in range(2,n+1): 
            dp[i] = dp[i-1] + dp[i-2]
        print(dp)
        return dp[n]

这个题目如何简单：dp数组的初始化和递推关系都已经给我们了，遍历顺序也是很直观

70. 爬楼梯

文档讲解：代码随想录

题目链接：. - 力扣（LeetCode）

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法(走一步或者直接走两步)。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。（当要爬到第三层时，我们已经在一层或者二层了，假设在一层，我们就还需要迈两个台阶，假设在第二层，只需迈一个台阶就可以，因为我们最后一步只能迈一步或者两步）

为什么三阶台阶只和一阶和二阶有关系？因为一步只能迈一步或者二步

同理4阶只能由2阶或者3阶迈上来，2阶再走两步，3阶再走1步

递推：当前这个阶有几种方法依赖于前两种状态

dp数组

dp[i]:达到第i阶有dp[i]种方法

递推公式

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

dp数组如何初始化

dp[0]=0,dp[1]=1，dp[2]=2

遍历顺序

从前向后遍历，从i=3开始遍历

debug

如果有问题就打印dp数组

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0]*(n+1) #因为有f(n)，所以数组长度是n+1
        dp[1] = 1
        if n > 1:
            dp[2] = 2
        for i in range(3,n+1): #当前状态只依赖于前两个状态，可以进行压缩
            dp[i] = dp[i-1] + dp[i-2]
        print(dp)
        return dp[n]

 最后这个题的代码与上一题差不多，但是从题意中看不出来呢？因为dp数组的定义与递推关系在题目中并没有明说

746. 使用最小花费爬楼梯

文档讲解：代码随想录

题目链接：. - 力扣（LeetCode）

dp数组的定义

如何定义dp数组呢？

我们的目标是求到达顶楼的最小消耗，上图中可以看出下标为3代表我们达到了楼顶，下标对应的值就表示为达到这楼的消耗

所以dp数组的含义就表示：到达i位置的最小花费是dp[i]

递推公式

一步可以跳1个台阶或者两个台阶

i可以由i-1跳了一步得到，花费就是cost[i-1]  一共就是dp[i] + cost[i-1]

也可以由i-2跳了两步得到,花费就是cost[i-2] 一共就是dp[i-2] + cost[i-2]

dp[i] = min(dp[i-2] + cost[i-2],dp[i] + cost[i-1])

dp数组如何初始化

初始位置可以选在0或1

dp[0] = 0,dp[1] = 0 

遍历顺序

从前向后遍历，从i=2开始遍历

debug

如果有问题就打印dp数组

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0]*(len(cost)+1)
        for i in range(2,len(cost)+1):
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
        return dp[len(cost)]