视频链接：https://www.bilibili.com/video/BV1GW411Q77S?p=9
动态规划原理（以爬楼梯为例）：
1. 原问题和子问题：
原问题：求第n阶台阶的所有走法数量
子问题：拆分为求第1，2，...，n - 1阶的走法数量
2. 状态：到每一阶台阶的走法
3. 边界：到第一阶走法为1种，到第二阶走法为2种
4. 状态转移方程：dp[n] = dp[n - 1] + dp[n - 2]，1.要不是从上一阶走一步上来，2.要不是从上两阶走两步上来（不存在分开走两步，因为这种情况已经考虑在1种类）
例题1：爬楼梯
（1）利用递归进行暴力回溯(超时）
class Solution: def climbStairs(self, n: int) -> int: def test(n): if n == 1 or n == 2: #只剩两个台阶时，要不一次走两个，要不一个一个走，共2种走法 return n return test(n - 1) + test(n - 2) #每次都有两种走法 return test(n)（2）动态规划
状态方程：
dp[0] = 1; dp[1] = 2; ... ; dp[n] = dp[n - 1] + dp[n - 2]
class Solution: def climbStairs(self, n: int) -> int: res = [1, 2] i = 2 while i < n: res.append(res[i - 1] + res[i - 2]) i += 1 return res[n - 1]其实动态规划和回溯法思路类似，只是思考的方向相反
暴力回溯法是从后向前推，把未知的部分当做一个整体，需要写出口以及递归的代码
动态规划是从前向后推，把以求得的部分当做一个整体，需要写入口以及递推的代码
例题2：打家劫舍
class Solution: def rob(self, nums: List[int]) -> int: if len(nums) == 0: return 0 if len(nums) == 1: return nums[0] nums[1] = max(nums[0], nums[1]) for i in range(2, len(nums)): nums[i] = max(nums[i - 1], nums[i] + nums[i - 2]) return nums[len(nums) - 1]状态方程有两种情况： 1. 取当前位置n的值，再加上n - 2之前的最大财宝数
2. 不取当前位置n的值，直接取n - 1位置时的最大财宝数
边界为：
1. 第一个位置为当前值
2. 第二个位置为第一个位置与第二个位置中的最大值
例题3：最大字段和
leetcode 53. 最大子序和 https://leetcode-cn.com/problems/maximum-subarray/
状态转移方程主要考虑的是dp[i]与前面状态的关系（如何由前面的状态得到），如dp[i - 1]或者dp[i - 2]的关系甚至dp[i - n]，找到关系就好做了，思维要放开
class Solution: def maxSubArray(self, nums: List[int]) -> int: for i in range(1, len(nums)): nums[i] = max(nums[i] + nums[i - 1], nums[i]) return max(nums)
例题4：找零钱
首先dp[i]代表什么不要搞错了，要解决的问题是可以组成的金额能否符合题目给出的金额。所以这里dp[i]存储的是组成目标金额的钞票张数，dp[i]可由i之前的数组成员表示。
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: porp = [0] * (amount + 1) for i in range(1, amount + 1): cur_min = float('inf') for j in coins: if i - j >= 0: cur_min = min(cur_min, porp[i - j]) porp[i] = cur_min + 1 if porp[amount] == float('inf'): return -1 return porp[amount]cur_min = float('inf')最小值初始化，很重要！！
cur_max = float('-inf')
