动态规划适用于能将问题拆分为子问题，且子问题互相离散独立的问题。
首先拆分大问题为几个小问题，解决小问题，然后将小问题的解记录下来，在解决大问题时利用小问题的解来计算大问题的解
1. 确定动态规划状态
2. 确定状态转移方程
3. 确定初始化条件
4. 确定输出状态
5. 考虑时间空间复杂度优化
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
for i in range(len(nums)):
for j in range(i):
if nums[i]>nums[j]:
dp[i]=max(dp[i],dp[j]+1)
个人认为这一步骤是动态规划最关键也是最困难的地方，在确定动态转移方程的时候可借助数学归纳法的方式，或者举出一个例子，在纸上完整得写出dp这个表格的值。然后总结出状态转移方程
3. 初始化
在这道题中，可将dp的值全部设置为1
**边界值的考虑主要在三个方面，这里需要特别注意
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0 #判断边界条件
dp=[1]*len(nums) #初始化dp数组状态
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]: #根据题目所求得到状态转移方程
dp[i] = max(dp[i],dp[j]+1)
return max(dp) #确定输出状态
整体来说
动态规划最详细的步骤以及需要考虑的点：
引自DataWhale LeetCode练习
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
输入:
"bbbab"
输出:
4
可用二维数组dp[i][j]来表示第i个字符到第j个字符之间的最长回文子序列长度是多少
下面仅列出状态转移方程以及初始化两个步骤
if s[i]==s[j]:
dp[i][j] = dp[i+1][j-1]+2
else:
dp[i][j] = max(dp[i][j-1],dp[i+1][j])
def longestPalindromeSubseq(self, s: str) -> int:
n=len(s)
dp=[[0]*n for _ in range(n)] #定义动态规划状态转移矩阵
for i in range(n): # 初始化对角线，单个字符子序列就是1
dp[i][i]=1
for i in range(n,-1,-1): #从右下角开始往上遍历
for j in range(i+1,n):
if s[i]==s[j]: #当两个字符相等时，直接子字符串加2
dp[i][j]= dp[i+1][j-1]+2
else: #不相等时，取某边最长的字符
dp[i][j]=max(dp[i][j-1],dp[i+1][j])
return dp[0][-1] #返回右上角位置的状态就是最长
个人水平有限，感觉本题十分难
题目描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 ‘h‘ 替换为 ‘r‘)
rorse -> rose (删除 ‘r‘)
rose -> ros (删除 ‘e‘)
解题思路
1. 第一步：确定动态规划状态
这个题目涉及到两个字符串，所以我们最先想到就是用两维数组来保存转移状态，定义dp[i][j]为字符串word1长度为i和字符串word2长度为j时，word1转化成word2所执行的最少操作次数的值。
2. 第二步：写出状态转移方程
关于这个问题的状态转移方程其实很难想到，这里提供的一个方向就是试着举个例子，然后通过例子的变化记录每一步变化得到的最少次数，来找到删除，插入，替换操作的状态转移方程具体应该怎么写。 我们采用从末尾开始遍历word1和word2， 当word1[i]等于word2[j]时，说明两者完全一样，所以i和j指针可以任何操作都不做，用状态转移式子表示就是dp[i][j]=dp[i-1][j-1]，也就是前一个状态和当前状态是一样的。 当word1[i]和word2[j]不相等时，就需要对三个操作进行递归了，这里就需要仔细思考状态转移方程的写法了。 对于插入操作，当我们在word1中插入一个和word2一样的字符，那么word2就被匹配了，所以可以直接表示为dp[i][j-1]+1 对于删除操作，直接表示为dp[i-1][j]+1 对于替换操作，直接表示为dp[i-1][j-1]+1 所以状态转移方程可以写成min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1)?
3. 第三步：考虑初始化条件
我们还是利用dp转移表法来找到状态转移的变化（读者可以自行画一张dp表，具体方法在求最长子序列中已经演示过了），这里我们用空字符串来额外加入到word1和word2中，这样的目的是方便记录每一步操作，例如如果其中一个是空字符串，那么另外一个字符至少的操作数都是1，就从1开始计数操作数，以后每一步都执行插入操作，也就是当i=0时，dp[0][j]=j,同理可得，如果另外一个是空字符串，则对当前字符串执行删除操作就可以了，也就是dp[i][0]=i?。
4. 第四步：考虑输出状态
在转移表中我们可以看到，可以从左上角一直遍历到左下角的值，所以最终的编辑距离就是最后一个状态的值，对应的就是dp[-1][-1]?。
5. 第五步：考虑对时间，空间复杂度的优化
和上题一样，这里由于dp[i][j]只和dp表中附近的三个状态（左边，右边和左上边）有关，所以同样可以进行压缩状态转移的空间存储，如果觉得有兴趣可以参考@Lyncien的解法,对于时间方面应该并没有可以优化的方法。
总结起来代码如下：
def minDistance(self, word1, word2):
#m,n 表示两个字符串的长度
m=len(word1)
n=len(word2)
#构建二维数组来存储子问题
dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
#考虑边界条件，第一行和第一列的条件
for i in range(n+1):
dp[0][i]=i #对于第一行，每次操作都是前一次操作基础上增加一个单位的操作
for j in range(m+1):
dp[j][0]=j #对于第一列也一样，所以应该是1,2,3,4,5...
for i in range(1,m+1): #对其他情况进行填充
for j in range(1,n+1):
if word1[i-1]==word2[j-1]: #当最后一个字符相等的时候，就不会产生任何操作代价，所以与dp[i-1][j-1]一样
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 #分别对应删除，添加和替换操作
return dp[-1][-1] #返回最终状态就是所求最小的编辑距离
本题内容印自DataWhale LeetCode练习
原文：https://www.cnblogs.com/cjqstudio/p/13551601.html