解体核心：穷举数据，求最值，将重叠子问题保存到备忘录，提炼最优子结构，符合「最优子结构」，子问题间必须互相独立，列出状态转移方程，找初始值。
最优子结构性质是动态规划问题的必要条件，一定是让你求最值的，遇到求最值的题，大部分考察动态规划

三大步骤

求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来避免我们的重复计算。动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

  • 第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
  • 第二步骤：列出正确的「状态转移方程」，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。
  • 第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1.定义数组元素的含义

首先我们来定义 dp[i] 的含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法，那我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法。

2.找出数组元素间的关系式

我们的目的是要求 dp[n]，动态规划的题，如你们经常听说的那样，就是把一个规模比较大的问题分成几个规模比较小的问题，然后由小的问题推导出大的问题。也就是说，dp[n] 的规模为 n，比它规模小的是 n-1, n-2, n-3…. 也就是说，dp[n] 一定会和 dp[n-1], dp[n-2]….存在某种关系的。我们要找出他们的关系。
那么问题来了，怎么找？
这个怎么找，是最核心最难的一个，我们必须回到问题本身来了，来寻找他们的关系式，dp[n] 究竟会等于什么呢？
对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式
一种是从第 n-1 级跳上来
一种是从第 n-2 级跳上来
由于我们是要算所有可能的跳法的，所以有 dp[n] = dp[n-1] + dp[n-2]。

3.找出初始条件

当 n = 1 时，dp[1] = dp[0] + dp[-1]，而我们是数组是不允许下标为负数的，所以对于 dp[1]，我们必须要直接给出它的数值，相当于初始值，显然，dp[1] = 1。一样，dp[0] = 0（0 个台阶，有人说是0种跳法，有人说是1种，我们暂时当作0种处理吧，不过无论哪种，都不影响问题都思路哈）。
于是得出初始值：
dp[0] = 0. dp[1] = 1，即 n <= 1时，dp[n] = n，还有当n = 2时也是初始值
跳台阶

  1. class Solution:
  2.     def numWays(self, n)
  3.         if n <= 2:
  4.             return n
  5.         a, b = 1, 2 
  6.         for i in range(3, n + 1): 
  7.             c = a + b 
  8.             a, b = b, c
  9.         return c

变态跳台阶

  1. class Solution:
  2.     def jumpFloorII(self, n):
  3.         if n <= 2:
  4.             return n
  5.         a = 2
  6.         for i in range(3, n + 1):
  7.             a = 2 * a
  8.         return a

1. 线性DP

买卖股票的最佳时机（只能买一次）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

  1. # 不保存dp结果，解决问题
  2. class Solution(object):
  3.     def maxProfit(self, prices):
  4.         if len(prices) < 2:
  5.             return 0
  7.         min_p = prices[0]
  8.         max_p = 0
  10.         for i in range(len(prices)):
  11.             min_p = min(min_p, prices[i]) 
  12.             max_p = max(max_p, prices[i] - min_p)
  13.         return max_p
  17. # 强行使用dp方法解决
  18. class Solution(object):
  19.     def maxProfit(self, prices):
  20.         if len(prices) < 2:
  21.             return 0
  23.         min_p = prices[0] 
  24.         dp = [0] * len(prices)
  26.         for i in range(1, len(prices)):
  27.             # 选出最小值
  28.             min_p = min(min_p, prices[i])
  29.             # 选出最大值
  30.             dp[i] = max(dp[i-1], prices[i] - min_p)
  31.         return dp[-1]

买卖股票的最佳时机 II（多次买卖）

可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  1. class Solution:
  2.     def maxProfit(self, prices):
  3.         if len(prices) < 2:
  4.             return 0
  5.         max_p = 0
  7.         for i in range(1, len(prices)):
  8.             tmp = prices[i] - prices[i-1]
  9.             if tmp > 0: 
  10.                 max_p += tmp
  11.         return max_p

买卖股票的最佳时机 III（可以买卖两次）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

  1. class Solution(object):
  2.     def maxProfit(self, prices):
  3.         if len(prices) < 2:
  4.             return 0
  5.         min_1 = min_2 = prices[0] # 第一二次买之前的最低价
  6.         max_1 = max_2 = 0
  8.         for i in range(len(prices)):
  9.             min_1 = min(min_1, prices[i])
  10.             max_1 = max(max_1, prices[i] - min_1)
  11.             min_2 = min(min_2, prices[i] - max_1) # p - pro_1 是用第一次的钱抵消了一部分第二次买的钱
  12.             max_2 = max(max_2, prices[i] - min_2)
  13.         return max_2

买卖股票的最佳时机 IV（可以买卖k次）

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

  1. class Solution(object):
  2.     def maxProfit(self, k, prices):
  3.         if len(prices) < 2:
  4.             return 0
  5.         min_p = [-prices[0]] * (k+1)
  6.         dp = [0] * (k+1)
  8.         for i in range(len(prices)):
  9.             for j in range(1, k + 1):
  10.                 min_p[j] = max(min_p[j], dp[j-1] - prices[i])
  11.                 dp[j] = max(dp[j], prices[i] + min_p[j])
  12.         return dp[-1]

买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

  1. class Solution(object):
  2.     def maxProfit(self, prices, fee):
  3.         if len(prices) < 2:
  4.             return 0
  5.         min_p = prices[0] + fee
  6.         max_p = 0
  8.         for i in range(1, len(prices)):
  9.             min_p = min(min_p, prices[i] + fee) 
  10.             if prices[i] > min_p:
  11.                 max_p += prices[i] - min_p
  12.                 min_p = prices[i]
  13.         return max_p

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

  1. class Solution:
  2.     def rob(self, nums):
  4.         # 方法一：优化空间复杂度为O（1），时间复杂度O（n）
  5.         max_p = 0
  6.         tmp = 0
  7.         for i in nums:
  8.             max_p, tmp = max(tmp + i, max_p), max_p
  9.         return max_p
  12.         # 方法二：非优化空间复杂度O（n）,时间复杂度O（n）
  13.         dp = [0] * (len(nums) + 2)
  15.         for i in range(2, len(nums) + 2):
  16.             # 如果偷了上一个，就不能再偷了，所以等于dp[i-1]
  17.             # 如果偷了上上个，那么就等于上上个加当前这个，即nums[i-2]
  18.             dp[i] = max(dp[i-1], dp[i-2] + nums[i-2])
  19.         return dp[-1]

打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

  1. class Solution:
  2.     def rob(self, nums):
  3.         # 比I版本多考虑一种即可，环形不能同时选择第一个和最后一个
  4.         def dynamicprocess(nums):
  5.             max_p = 0
  6.             tmp = 0
  7.             for i in nums:
  8.                 max_p, tmp = max(tmp + i, max_p), max_p
  9.             return max_p
  11.         if len(nums) != 1:
  12.             return max(dynamicprocess(nums[:-1]), dynamicprocess(nums[1:]))
  13.         else: 
  14.             return nums[0]
  16.         # 方法二：非优化空间复杂度O（n）,时间复杂度O（n）
  17.         def dynamicprocess(nums):
  18.             dp = [0] * (len(nums) + 2)
  19.             for i in range(2, len(nums) + 2):
  20.                 dp[i] = max(dp[i-1], dp[i-2] + nums[i-2])
  21.             return dp[-1]
  23.         if len(nums) != 1:
  24.             return max(dynamicprocess(nums[:-1]), dynamicprocess(nums[1:]))
  25.         else: 
  26.             return nums[0]

打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

  1. class Solution(object):
  2.     def rob(self, root):
  4.         def dynamicprocess(root):
  5.             if not root: 
  6.                 return 0, 0  # 偷，不偷
  8.             left = dynamicprocess(root.left)
  9.             right = dynamicprocess(root.right)
  10.             # 偷当前节点, 则左右子树都不能偷
  11.             v1 = root.val + left[1] + right[1]
  12.             # 不偷当前节点, 则取左右子树中最大的值
  13.             v2 = max(left) + max(right)
  14.             return v1, v2
  16.         return max(dynamicprocess(root))

最大连续子序和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

  1. 状态定义： 设动态规划列表 dp ，dp[i]代表以元素 nums[i] 为结尾的连续子数组最大和。
    • 为何定义最大和 dp[i] 中必须包含元素 nums[i] ：保证 dp[i] 递推到 dp[i+1] 的正确性；如果不包含 nums[i] ，递推时则不满足题目的 连续子数组 要求。
  2. 转移方程： 若 dp[i−1]≤0 ，说明 dp[i−1] 对 dp[i] 产生负贡献，即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。
    • 当 dp[i−1]>0 时：执行 dp[i]=dp[i−1]+nums[i] ；
    • 当 dp[i−1]≤0 时：执行 dp[i]=nums[i] ；
  3. 初始状态： dp[0]=nums[0]，即以 nums[0] 结尾的连续子数组最大和为 nums[0] 。

  4. 返回值： 返回 dp 列表中的最大值，代表全局最大值。 ```python class Solution: def maxSubArray(self, nums):

    1.  # 方法一：dp版本
    2.  dp = [0] * len(nums)
    3.  dp[0] = nums[0]
    5.  for i in range(1, len(nums)):
    6.      dp[i] = max(dp[i-1] + nums[i], nums[i])
    7.  return max(dp)
  1.     # 方法二：简化版
  2.     max_sum = nums[0]
  4.     for i in range(1, len(nums)):
  5.         if nums[i-1] > 0:
  6.             nums[i] += nums[i-1] 
  7.         max_sum = max(nums[i], max_sum)
  8.     return max_sum
  1. <a name="ddb99035d7f8c4361c4f1caa4a2643cb"></a>
  2. ## [最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)***
  3. 给定一个无序的整数数组，找到其中最长上升子序列的长度。<br />输入: [10,9,2,5,3,7,101,18]<br />输出: 4<br />解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
  5. 1. **状态定义： **设动态规划列表 dp ，dp[i] 代表以元素 nums[i] 前 i 个数字的最长子序列长度。
  6. 1. **转移方程：** 若j∈[0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断：
  7.    - 当 nums[i] > nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j] + 1 ；
  8.    - 当 nums[i]<=nums[j] 时： nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。
  9.    - **转移方程：** dp[i] = max(dp[i], dp[j] + 1)。
  10. 3. **初始状态：** dp[i] 所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1。
  11. 3. **返回值：** 返回 dp 列表中的最大值，代表全局最大值。
  12. ```python
  13. class Solution:
  14.     def lengthOfLIS(self, nums):
  15.         # 方法一：动态规划，时间复杂度：O(n^2)
  16.         if not nums: 
  17.             return 0
  18.         dp = [1 for _ in range(len(nums))]
  20.         for i in range(len(nums)):
  21.             for j in range(i):
  22.                 if nums[j] < nums[i]:  # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
  23.                     dp[i] = max(dp[i], dp[j] + 1)
  24.         return max(dp)
  27.         # 方法二：最优解，动态规划+二分查找，时间复杂度：O(nlogn)
  28.         max_p = 0
  29.         top = []
  30.         for i in range(len(nums)):
  31.             poker = nums[i]
  32.             # 二分搜索top中大于等于poker的左侧边界，找poker要落的堆
  33.             left, right = 0, len(top)-1
  34.             while left <= right:
  35.                 mid = (left + right) // 2
  36.                 if top[mid] >= poker:
  37.                     right = mid - 1
  38.                 else:
  39.                     left = mid + 1
  40.             if left < len(top):
  41.                 top[left] = poker
  42.             else:
  43.                 max_p += 1
  44.                 top.append(poker)
  45.         return max_p

递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

  1. class Solution(object):
  2.     def increasingTriplet(self, nums):
  3.         min_p = float('inf') # 次小的
  4.         min_pp = float('inf') # 最小的
  6.         for i in nums:
  7.             min_p = min(min_p, i)
  8.             # 比次小的大，说明i应该当头
  9.             if i > min_p:
  10.                 min_pp = min(min_pp, i)
  11.             # 比最小的都大，说明找到了
  12.             if i > min_pp:
  13.                 return True
  14.         return False

最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续的的递增序列。
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。

  1. 状态定义： 设动态规划列表 dp ，dp[i]代表以元素 nums[i] 为结尾的最长且连续的的递增序列的长度。
  2. 转移方程： 若nums[i] < nums[i-1]，说明dp[i−1] 对 dp[i] 没有产生贡献或产生负贡献。
    • 当 nums[i] > nums[i-1] 时：执行 dp[i] = dp[i-1] + 1 ；
    • 当 nums[i] < nums[i-1] 时：执行 pass ；
  3. 初始状态：

  4. 返回值： 返回 dp 列表中的最大值，代表全局最大值。

    1. class Solution:
    2.  def findLengthOfLCIS(self, nums):
    3.      # 方法一：动态规划
    4.      if not nums:
    5.          return 0
    6.      dp = [1 for _ in range(len(nums))]
    8.      for i in range(1 ,len(nums)):
    9.          if nums[i] > nums[i-1]:
    10.              dp[i] = dp[i-1] + 1
    11.      return max(dp)
    13.      # 方法二 
    14.      if not nums:
    15.          return 0
    16.      lists = [nums[0]]
    17.      max_len = 1
    19.      for i in range(1, len(nums)):
    20.          if nums[i] > nums[i - 1]:
    21.              lists.append(nums[i])
    22.          else:
    23.              del lists[:]
    24.              lists.append(nums[i]) 
    25.          max_list = lists
    26.          if len(max_list) > max_len:
    27.              max_len = len(max_list)
    28.      return max_len

    最长公共子序列

    输入：text1 = “abcde”, text2 = “ace”
    输出：3
    解释：最长公共子序列是 “ace”，它的长度为 3。

第一步，一定要明确 **dp** 数组的含义。对于两个字符串的动态规划问题，套路是通用的
比如说对于字符串 s1 和 s2，一般来说都要构造一个这样的 DP table：
动态规划 - 图1
为了方便理解此表，我们暂时认为索引是从 1 开始的，待会的代码中只要稍作调整即可。其中，dp[i][j] 的含义是：对于 s1[1..i] 和 s2[1..j]，它们的 LCS 长度是 dp[i][j]。
比如上图的例子，d[2][4] 的含义就是：对于 "ac" 和 "babc"，它们的 LCS 长度是 2。我们最终想得到的答案应该是 dp[3][6]。
第二步，定义 base case
我们专门让索引为 0 的行和列表示空串，dp[0][..] 和 dp[..][0] 都应该初始化为 0，这就是 base case。
比如说，按照刚才 dp 数组的定义，dp[0][3]=0 的含义是：对于字符串 "" 和 "bab"，其 LCS 的长度为 0。因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0。
第三步，找状态转移方程
这是动态规划最难的一步，不过好在这种字符串问题的套路都差不多，权且借这道题来聊聊处理这类问题的思路。
状态转移说简单些就是做选择，比如说这个问题，是求 s1 和 s2 的最长公共子序列，不妨称这个子序列为 lcs。那么对于 s1 和 s2 中的每个字符，有什么选择？很简单，两种选择，要么在 lcs 中，要么不在。

  1. 当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的当前位相等，所以最长公共子序列又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + 1；举个例子，比如对于 ac 和 bc 而言，他们的最长公共子序列的长度等于 a 和 c 的最长公共子序列长度 0 + 1 = 1。
  2. 当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。举个例子，比如对于 ace 和 bc 而言，他们的最长公共子序列的长度等于 ① ace 和 b 的最长公共子序列长度0 与 ② ac 和 bc 的最长公共子序列长度1 的最大值，即 1。
  5. class Solution(object):
  6.     def longestCommonSubsequence(self, text1, text2):
  7.         dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
  8.         # 进行状态转移
  9.         for i in range(1, len(text1) + 1):
  10.             for j in range(1, len(text2) + 1):
  11.                 if text1[i-1] == text2[j-1]:
  12.                     dp[i][j] = dp[i-1][j-1] + 1
  13.                 else:
  14.                     dp[i][j] = max(dp[i][j-1], dp[i-1][j])
  15.         return dp[-1][-1]

每日温度

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

  1. class Solution(object):
  2.     def dailyTemperatures(self, T):
  3.         stack = []
  4.         dp = [0 for _ in range(len(T))]
  6.         for i in range(len(T)):
  7.             while stack and T[stack[-1]] < T[i]:
  8.                 dp[stack[-1]] = i - stack[-1]
  9.                 stack.pop()
  10.             stack.append(i)
  11.         return dp

最长回文子串*

给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
输入：s = “cbbd”
输出：”bb”
输入：s = “a”
输出：”a”

  1. class Solution(object):
  2.     def longestPalindrome(self, s):
  4.         # 方法一：动态规划，dp[j][i] 表示字符串从 j 到 i 是否是为回文串，即当 s[j] == s[i] 如果 dp[j+1][i-1] 也是回文串，那么字符串从 j 到 i 也是回文串，即 dp[j][i] 为真。
  5.         dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
  6.         res = ""
  7.         for i in range(len(s)):
  8.             for j in range(i + 1):
  9.                 if s[i] == s[j] and (i-j+1 <= 3 or dp[j+1][i-1]):
  10.                     dp[j][i] = 1
  11.                     # key表示以len长度比大小
  12.                     res = max(res, s[j:i+1], key=len)   
  13.         return res
  15.         # 方法二：动态规划，自底向上，从长度1 -> n 列举所有子串
  16.         dp = [[1 for _ in range(len(s))] for _ in range(len(s))]
  17.         left, right = 0, 0 #长度为1时
  19.         for i in range(1, len(s)):
  20.              for j in range(len(s)-i):
  21.                 if s[j] == s[j+i] and dp[j+1][j+i-1]:
  22.                     dp[j][j+i] = 1 
  23.                     left, right = j, j+i
  24.                 else:
  25.                     dp[j][j+i] = 0
  26.         return s[left: right+1]
  28.        # 方法三：双指针，这种最好理解，把每个字母当成回文串的中心
  29.         self.res = ""
  30.         def dfs(left, right):
  31.             # 左边和右边都不出界且相等
  32.             while left >= 0 and right < len(s) and s[left] == s[right]:
  33.                 left -= 1
  34.                 right += 1
  35.             # 更新最大值
  36.             if right - left -1 > len(self.res):
  37.                 self.res = s[left+1:right]
  38.         # 这里要考虑两种情况，回文串的长度为奇数或者偶数情况。
  39.         for i in range(len(s)):
  40.             dfs(i, i)
  41.             dfs(i, i+1)
  42.         return self.res

礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

  1. class Solution:
  2.     def maxValue(self, grid):
  3.         # 方法一：倒着推
  4.         # 我们利用一个比原格子多一行，一列的表格反向计算从每个格子出发的最大值。多加的行和列初始为 00，可以用来简化边界判断。
  5.         # 对于每一个格子，它的最优解就是本格子的值，加上分别向下和向右能得到的最大值。所以我们保证每一格贪心即可，最终到达左上角。
  6.         if not grid : 
  7.             return 0
  8.         dp = [[0 for _ in range(len(grid[0]) + 1)] for _ in range(len(grid) + 1)]
  9.         for i in (range(len(grid))[::-1]):
  10.             for j in (range(len(grid[0]))[::-1]): 
  11.                 dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + grid[i][j]
  12.         return dp[0][0]
  14.         # 方法二：正向推
  15.         if not grid:
  16.             return 0
  17.         dp = [[0 for _ in range(len(grid[0]) + 1)] for _ in range(len(grid) + 1)]
  18.         for i in range(1, len(grid) + 1):
  19.             for j in range(1, len(grid[0]) + 1):
  20.                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]
  21.         return dp[-1][-1]

完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
输入：n = 13
输出：2
解释：13 = 4 + 9

  1. class Solution(object):
  2.     def numSquares(self, n):
  3.         dp = [i for i in range(n+1)]
  4.         for i in range(2, n+1):
  5.             for j in range(1, int(i**(0.5)) + 1):
  6.                 dp[i] =  min(dp[i], dp[i-j*j]+1)
  7.         return dp[-1]

剪绳子*

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

  1. class Solution:
  2.     def cuttingRope(self, n):
  3.         dp = [0 for _ in range(n + 1)]  # dp[0] dp[1]其实没用
  4.         dp[2] = 1
  5.         res = -1
  7.         for i in range(3, n + 1):
  8.             for j in range(i):
  9.                 dp[i] = max(dp[i], max((i - j) * j, j * dp[i - j]))
  10.         return dp[-1]
  13. class Solution:
  14.     def cuttingRope(self, n):
  15.         if n < 4:
  16.             return n - 1
  17.         if n == 4:
  18.             return n
  20.         res = 1
  21.         while n > 4:
  22.             res *= 3
  23.             n -= 3
  24.         return res * n

2. 背包DP

一个背包，往里装东西，重量w=[2,3,4,5] 价值v=[3,4,5,6] 如果你的容量为C=8，每个物品只有一个，求你能装入背包的最大价值

背包问题模版

  1. dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)]
  2. dp[0][..] = 0
  3. dp[..][0] = 0
  5. for i in [1..N]:
  6.     for w in [1..W]:
  7.         dp[i][w] = max(
  8.             把物品 i 装进背包,
  9.             不把物品 i 装进背包
  10.         )
  11. return dp[N][W]

普通背包问题（每个物品只有一个）

image.png
一个背包，往里装东西，重量w=[2,3,4,5] 价值v=[3,4,5,6] 如果你的容量为C=8，每个物品只有一个，求你能装入背包的最大价值

  1. def pack1(w, v, C):  # 每个东西只能选择一次
  2.     dp = [[0 for _ in range(C + 1)] for _ in range(len(w) + 1)]
  4.     for i in range(1, len(w) + 1):
  5.         for j in range(1, C + 1):
  6.             if j < w[i - 1]:  # 如果剩余容量不够新来的物体 直接等于之前的
  7.                 dp[i][j] = dp[i-1][j]
  8.             else:
  9.                 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
  10.     return dp[len(w)][C]

解释：

  1. dp[i][j] 表示：对于前 i 个物品，当前背包的容量为 j 时，这种情况下可以装下的最大价值是 dp[i][j]。
  2. 如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。
  3. 如果你把这第 i 个物品装入了背包，那么 dp[i][j] 应该等于 dp[i-1][j-w[i-1]] + v[i-1]。
  4. 首先，由于 i 是从 1 开始的，所以 v 和 w 的索引是 i-1 时表示第 i 个物品的价值和重量。
  5. 而 dp[i-1][j-w[i-1]] 也很好理解：你如果装了第 i 个物品，就要寻求剩余重量 j - w[i-1] 限制下的最大价值，加上第 i 个物品的价值 v[i-1]。

完全背包问题（所有物品无限个）

还是原来的问题，上次是每个物体只能用1次，现在改成无限次，转移方程只需要修改一点即可dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]] + v[i-1]) 只需要把后面的i-1 -> i 即可
image.png

  1. def pack2(w, v, C): #每个东西能选择多次 完全背包问题
  3.     dp = [[0 for _ in range(C + 1)] for _ in range(len(w) + 1)]
  4.     for i in range(1, len(w) + 1):
  5.         for j in range(1, C + 1):
  6.             if j < w[i-1]:
  7.                 dp[i][j] = dp[i-1][j]
  8.             else:
  9.                 dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]] + v[i-1]) #改这里即可
  10.     return dp[len(w)][C]

零钱兑换（求最少的硬币个数）

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1

  1. class Solution(object):
  2.     def coinChange(self, coins, amount):
  4.         dp = [amount + 1 for _ in range(amount+1)]
  5.         dp[0] = 0
  7.         for i in range(amount+1):
  8.             for j in coins:
  9.                 if (i-j < 0):
  10.                     continue
  11.                 dp[i] = min(dp[i], dp[i-j] + 1)
  13.         if dp[amount] != amount + 1:
  14.             return dp[amount] 
  15.         else: 
  16.             return -1

零钱兑换 II（求硬币组合数）

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

  1. class Solution:
  2.     def change(self, amount, coins):
  4.         dp = [0] * (amount + 1)
  5.         dp[0] = 1
  7.         for i in coins:
  8.             for j in range(i, amount + 1):
  9.                 dp[j] += dp[j-i]
  10.         return dp[amount]

3. 递推型DP

斐波那契数列

方法一：递归
时间复杂度: O(2^n)

  1. class Solution:
  2.     def Fibonacci(self, n):
  3.         if n == 0:
  4.             return 0
  5.         if n == 1:
  6.             return 1
  7.         return self.Fibonacci(n - 1) + self.Fibonacci(n - 2)
  9. # f(n) = f(n-1) + f(n-2)

方法二：动态规划
时间复杂度: O(n)

  1. class Solution:
  2.     def Fibonacci(self, n):
  3.         a, b = 0, 1
  4.         for _ in range(n):
  5.             a, b = b, a + b
  6.         return a

跳台阶

  1. class Solution:
  2.     def numWays(self, n)
  3.         if n <= 2:
  4.             return n
  5.         a, b = 1, 2 
  6.         for i in range(3, n + 1): 
  7.             c = a + b 
  8.             a, b = b, c
  9.         return c

变态跳台阶（一次可以跳多阶）

  1. class Solution:
  2.     def jumpFloorII(self, n):
  3.         if n <= 2:
  4.             return n
  5.         a = 2
  6.         for i in range(3, n + 1):
  7.             a = 2 * a
  8.         return a