Leetcode【712、746、877】

问题描述：【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）：

方法2（区间 DP）：

更一般的来说，我们用动态规划来解决这个问题：

• 用 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