动态规划题目特点：

1、计数

例：有多少种方式走到右下角，有多少种方法选出K个数使得和是sum。等

2、求最大最小值

例：从左上角走到右下角路径的最大数字和，最长上升子序列长度。等

3、求存在性

例：取石子游戏，先手是否必胜，能不能选出K个数使得和为sum。等

动态规划做题步骤

动态规划组成部分一：确定状态

状态在动态规划中的作用属于定海神针
简单的说，解动态规划的时候需要开一个数组，数组的每个元素dp[i]或者dp[i][j]代表什么。类似于解数学题中的X，Y，Z代表什么
确定状态需要两个意识：1、最后一步；2、子问题
最后一步：指的是得出最优解的最后一个步骤是什么。
子问题：去掉最后一步，求上一步最优解是什么。

动态规划组成部分二：转移方程

例如：斐波那契数列
动态规划 - 图1
转移方程为：dp[n] = dp[n - 1] + dp[n - 2]

动态规划组成部分三：初始条件和边界情况

例如：斐波那契数列
动态规划 - 图2
初始条件为：dp[0] = 0，dp[1] = 1

动态规划组成部分四：计算顺序

确认计算顺序，一般为从小到大
二维的话一般为从上到下，从左到右

leetcode62题：不同路径

动态规划组成部分一：确定状态

最后一步：

无论机器人用何种方式到达右下角：总有最后挪动的一步：向右或者向下
右下角坐标设为(m-1, n-1)
那么前一步机器人一定是在(m-2, n-1)或者(m-1, n-2)

子问题：

那么，如果机器人有X种方式从左上角走到(m-2,n-1)，有Y种方式从左上角走到(m-1,n-2)，则机器人有X+Y种方式走到(m-1, n-1)
问题转化为，机器人有多少种方式从左上角走到(m-2, n-1)和(m-1, n-2)
状态：dp[i][j]为机器人有多少种方式从左上角走到(i,j)。

动态规划组成部分二：转移方程

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

动态规划组成部分三：初始条件和边界情况

初始条件：dp[0][0] = 1
边界情况：dp[0][i] = 1和dp[j][0] = 1，即第一行和第一列都只有一种方式走到

动态规划组成部分四：计算顺序

f[0][0]= 1
计算第0行: f[0][0], f[0][1], … f[0][n-1]
计算第1行: f[1][0], f[1][1], … f[1][n-1]
….
计算第m-1行: f[m-1][0], f[m-1][1], …. f[m-1][n-1]

  1. # 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 
  2. # 
  3. #  机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 
  4. # 
  5. #  问总共有多少条不同的路径？ 
  6. # 
  7. #  
  8. # 
  9. #  示例 1： 
  10. # 
  11. #  
  12. # 输入：m = 3, n = 7
  13. # 输出：28 
  14. # 
  15. #  示例 2： 
  16. # 
  17. #  
  18. # 输入：m = 3, n = 2
  19. # 输出：3
  20. # 解释：
  21. # 从左上角开始，总共有 3 条路径可以到达右下角。
  22. # 1. 向右 -> 向下 -> 向下
  23. # 2. 向下 -> 向下 -> 向右
  24. # 3. 向下 -> 向右 -> 向下
  25. #  
  26. # 
  27. #  示例 3： 
  28. # 
  29. #  
  30. # 输入：m = 7, n = 3
  31. # 输出：28
  32. #  
  33. # 
  34. #  示例 4： 
  35. # 
  36. #  
  37. # 输入：m = 3, n = 3
  38. # 输出：6 
  39. # 
  40. #  
  41. # 
  42. #  提示： 
  43. # 
  44. #  
  45. #  1 <= m, n <= 100 
  46. #  题目数据保证答案小于等于 2 * 109 
  47. #  
  48. #  Related Topics 数学 动态规划 组合数学 
  49. #  👍 1384 👎 0
  52. # leetcode submit region begin(Prohibit modification and deletion)
  53. class Solution:
  54.     def uniquePaths(self, m: int, n: int) -> int:
  55.         dp = [[0] * n for _ in range(m)]    # 初始化dp数组
  56.         for i in range(1, m):
  57.             for j in range(1, n):
  58.                 if i == 0 or j == 0:
  59.                     dp[i][j] = 1    # 初始化dp数组的初始条件和边界情况
  60.                 else:
  61.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1]  # 动态转移方程
  62.         return dp[m - 1][n - 1]
  63. # leetcode submit region end(Prohibit modification and deletion)

leetcode55题：跳跃游戏

动态规划组成部分一：确定状态

最后一步：

如果能跳到最后一个下标，我们考虑跳的最后一步是从下标 i 跳过去的 i < n - 1
那么需要满足 i 下标是可以跳到的，并且最后一步不超过跳跃的最大距离：n - 1 - i < nums[i]

子问题：

我们需要知道是否能跳到 i 下标
问题转化为，是否能跳到下标 i
状态：dp[i]为是否能跳到 i 下标。

动态规划组成部分二：转移方程

dp[j] = OR0<=i<j(dp[i] and i + a[i] >= j) 从0到 i 枚举 i 是否能跳到 j

动态规划组成部分三：初始条件和边界情况

dp[0] = True，因为一开始就在0下标

动态规划组成部分四：计算顺序

计算 dp[1]，dp[2]….dp[n-1]

  1. # 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 
  2. # 
  3. #  数组中的每个元素代表你在该位置可以跳跃的最大长度。 
  4. # 
  5. #  判断你是否能够到达最后一个下标。 
  6. # 
  7. #  
  8. # 
  9. #  示例 1： 
  10. # 
  11. #  
  12. # 输入：nums = [2,3,1,1,4]
  13. # 输出：true
  14. # 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
  15. #  
  16. # 
  17. #  示例 2： 
  18. # 
  19. #  
  20. # 输入：nums = [3,2,1,0,4]
  21. # 输出：false
  22. # 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
  23. #  
  24. # 
  25. #  
  26. # 
  27. #  提示： 
  28. # 
  29. #  
  30. #  1 <= nums.length <= 3 * 104 
  31. #  0 <= nums[i] <= 105 
  32. #  
  33. #  Related Topics 贪心 数组 动态规划 
  34. #  👍 1810 👎 0
  37. # leetcode submit region begin(Prohibit modification and deletion)
  38. class Solution:
  39.     def canJump(self, nums: List[int]) -> bool:
  40.         n = len(nums)
  41.         dp = [False for _ in range(n)]
  42.         dp[0] = True
  43.         for j in range(1, n):
  44.             dp[j] = False
  45.             for i in range(j):
  46.                 if dp[i] and i + nums[i] >= j:
  47.                     dp[j] = True
  48.                     break
  49.         return dp[-1]
  50. # leetcode submit region end(Prohibit modification and deletion)

leetcode300题：最长上升子序列

动态规划组成部分一：确定状态

最后一步：

枚举0<=j

子问题：

计算 i - 1的长度值

动态规划组成部分二：转移方程

枚举0<=j nums[j]：dp[i] = max(dp[i], dp[j] + 1)；nums[i] < nums[j]：dp[i] = 1

  1. # 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 
  2. # 
  3. #  子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子
  4. # 序列。 
  5. #  
  6. # 
  7. #  示例 1： 
  8. # 
  9. #  
  10. # 输入：nums = [10,9,2,5,3,7,101,18]
  11. # 输出：4
  12. # 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
  13. #  
  14. # 
  15. #  示例 2： 
  16. # 
  17. #  
  18. # 输入：nums = [0,1,0,3,2,3]
  19. # 输出：4
  20. #  
  21. # 
  22. #  示例 3： 
  23. # 
  24. #  
  25. # 输入：nums = [7,7,7,7,7,7,7]
  26. # 输出：1
  27. #  
  28. # 
  29. #  
  30. # 
  31. #  提示： 
  32. # 
  33. #  
  34. #  1 <= nums.length <= 2500 
  35. #  -104 <= nums[i] <= 104 
  36. #  
  37. # 
  38. #  
  39. # 
  40. #  进阶： 
  41. # 
  42. #  
  43. #  你能将算法的时间复杂度降低到 O(n log(n)) 吗? 
  44. #  
  45. #  Related Topics 数组 二分查找 动态规划 
  46. #  👍 2453 👎 0
  49. # leetcode submit region begin(Prohibit modification and deletion)
  50. class Solution:
  51.     def lengthOfLIS(self, nums: List[int]) -> int:
  52. # leetcode submit region end(Prohibit modification and deletion)