首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode【712、746、877】

Leetcode【712、746、877】

作者头像
echobingo
发布2019-06-14 10:44:42
3820
发布2019-06-14 10:44:42
举报
问题描述:【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):

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

  • 用 dpi 表示 pilesi~pilesj 之间先手可以赢后手的分数,并且此时先手取的是 i 或者 j。那么最后的结果就是看 dp0 (n 是 piles 的长度) 是否大于 0。
  • 对于某个范围 dpi 来说,如果先手取 i,那么 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 的典型题目。

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
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019.06.09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题描述:【DP】712. Minimum ASCII Delete Sum for Two Strings
  • 解题思路:
  • Python3 实现:
  • 问题描述:【DP】746. Min Cost Climbing Stairs
  • 解题思路:
  • Python3 实现:
  • 问题描述:【DP、Trick】877. Stone Game
  • 解题思路:
  • Python3 实现(区间 DP):
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档