动态规划算法（Dynamic Programming) 简介
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，在计算时将子问题的解储存起来，避免在后续子问题之间进行递推时的重复计算（称作记忆化搜索），最终高效获得计算结果。
动态规划被广泛应用于求解具有重叠子问题和最优子结构的问题。重叠子问题指在求解某个问题时，使用了与该问题相关的子问题，而这些子问题可能会被反复运算，因此将它们的结果保存下来可以避免重复计算；最优子结构则是指问题的最优解是由其子问题的最优解组合而成的，也就是说，子问题的最优解一定是问题的最优解的组成部分。
使用场景
- 最优化原理 - 如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
- 无后效性 - 即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
- 有重叠子问题 - 即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。
实施步骤——动态规划五步曲
- 划分阶段，往往使用“自底向上”的方式；
- 确定dp数组、下标含义；
- 确定递推公式；
- 确定初始化方式、遍历顺序及边界条件；
- 举例推导dp数组进行验证。
例题1- 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for _ in range(n)] for _ in range(m)] #对格子进行初始化
dp[0] = [1 for _ in range(n)] #对第一行进行初始化
for i in range(1, m): #对第一列进行初始化
dp[i][0] = 1
for i in range(1, m): #对剩下的格子计算路径条数
for j in range(1, n):
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[-1][-1]
例题2- 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 “bb” 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2)
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]