读完题目后发现:把两个字符串中多余的字符删除后,最后留下的字符串是两个字符串的最长公共子序列。因此这道题可以像最长公共子序列一样,采用动态规划的思想解决:常考的经典算法--最长公共子序列(LCS)与最长公共子串(DP)。
dp[len(s1)+1][len(s2)+1]
,其中 dp[i][j]
表示字符串 s1 的前 i 个字符与字符串 s2 前 j 个字符的最小ASCll 删除和。最后,dp[-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)
,初始化列。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[i] = min(dp[i-1], dp[i-2]) + cost[i]
。dp[-1]
和 dp[-2]
中的较小值。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)
方法1(必胜法,直接返回 True):
方法2(区间 DP):
更一般的来说,我们用动态规划来解决这个问题:
dp[i][j] = piles[i] - dp[i+1][j]
**,因为 pilesi+1~pilesj 是后手赢先手的分数,所以此时先手选择 pilesi 和它做差;**当然先手也可以取 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,所以得到的最优子结构先是小范围的,然后慢慢扩展到大范围(dp0),因此在编程时要注意双层循环的遍历顺序。这种遍历方式与 Leetcode 【647】求一个字符串的不同回文子串个数 中的 DP 做法的遍历方式相同。实际上它也是区间 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