问题描述：【DP】712. Minimum ASCII Delete Sum for Two Strings
解题思路：
读完题目后发现：把两个字符串中多余的字符删除后，最后留下的字符串是两个字符串的最长公共子序列。因此这道题可以像最长公共子序列一样，采用动态规划的思想解决：常考的经典算法--最长公共子序列（LCS）与最长公共子串(DP)。
- 创建
dp[len(s1)+1][len(s2)+1]，其中dp[i][j]表示字符串 s1 的前 i 个字符与字符串 s2 前 j 个字符的最小ASCll 删除和。最后，dp[-1][-1]就是答案。 - 对照最长公共子序列，可以容易的发现状态转移方程如下：
1、dp[i][j] = dp[i-1][j-1], if s1[i-1] == s2[j-1]（不删除字符）；
2、dp[i][j] = min(dp[i-1][j]+ord(s1[i-1]), dp[i][j-1]+ord(s2[j-1])), if s1[i-1] != s2[j-1]（采取两者中代价最小的删除方式）。 - 初始化时，
dp[0][0] = 0，而第 0 行和第 0 列的值应该是前面状态的累加，即：
1、dp[i][0] = dp[i-1][0] + ord(s1[i-1]), i = 1 to (len(s1)+1)，初始化行；
2、dp[0][i] = dp[0][i-1] + ord(s2[i-1]), i = 1 to (len(s2)+1)，初始化列。
Python3 实现：
class Solution:
def minimumDeleteSum(self, s1: str, s2: str) -> int:
lens1, lens2 = len(s1), len(s2)
dp = [[float("inf")] * (lens2+1) for _ in range(lens1+1)]
dp[0][0] = 0
for i in range(1, lens1+1): # 初始化行
dp[i][0] = dp[i-1][0] + ord(s1[i-1])
for i in range(1, lens2+1): # 初始化列
dp[0][i] = dp[0][i-1] + ord(s2[i-1])
for i in range(1, lens1+1):
for j in range(1, lens2+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j]+ord(s1[i-1]), dp[i][j-1]+ord(s2[j-1]))
return dp[-1][-1]
问题描述：【DP】746. Min Cost Climbing Stairs
解题思路：
- 简单 DP，
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。 -
注意：最后的结果是
dp[-1]和dp[-2]中的较小值。 - 实际上只需要使用两个变量保存前两个状态即可，空间复杂度可以将为 O(1)。
Python3 实现：
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = [0] * len(cost)
dp[0], dp[1] = cost[0], cost[1]
for i in range(len(cost)):
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
return dp[-1] if dp[-1] < dp[-2] else dp[-2]
print(Solution().minCostClimbingStairs([1,3,2,4])) # 3 (1->2)
问题描述：【区间DP、Trick】877. Stone Game
解题思路：
方法1（必胜法，直接返回 True）：
更一般的来说，我们用动态规划来解决这个问题：
- 用 dp[i][j] 表示 piles[i]~piles[j] 之间先手可以赢后手的分数，并且此时先手取的是 i 或者 j。那么最后的结果就是看 dp[0][n-1] (n 是 piles 的长度) 是否大于 0。
-
对于某个范围 dp[i][j] 来说，如果先手取 i，那么
dp[i][j] = piles[i] - dp[i+1][j]，因为 piles[i+1]~piles[j] 是后手赢先手的分数，所以此时先手选择 piles[i] 和它做差；当然先手也可以取 j，那么dp[i][j] = piles[j] - dp[i][j-1]。 - 先手应该选取这两者的极大值，即
dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1])。
注意：因为是区间 DP，所以得到的最优子结构先是小范围的，然后慢慢扩展到大范围（dp[0][n-1]），因此在编程时要注意双层循环的遍历顺序。这种遍历方式与 Leetcode 【647】求一个字符串的不同回文子串个数 中的 DP 做法的遍历方式相同。实际上它也是区间 DP 的典型题目。
Python3 实现（区间 DP）：
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
lens = len(piles)
dp = [[0] * lens for _ in range(lens)]
for j in range(lens):
dp[j][j] = piles[j]
for i in range(j-1, -1, -1):
dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1])
return dp[-1][-1] > 0
print(Solution().stoneGame([5,6,1,2,6,5]) # True
