【Leetcode】top 100 多维动态规划

这篇具有很好参考价值的文章主要介绍了【Leetcode】top 100 多维动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

62 不同路径

一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步,机器人试图达到网格的右下角,问总共有多少条不同的路径?

分析:dp[i][j] 代表走到 (i, j) 的路径总和数

递推规律:dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始条件:dp[0][:] = 1 dp[:][0] = 1

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[1]*n for _ in range(m)]
        for i in range(1, m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]
    
# 滚动数组更新,记录dp可同时表示i-1和i行
# 因为更新dp[i][j]时需要用到的dp[i-1][j]未被更新,而dp[i][j-1]已更新
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [1]*n
        for i in range(1, m):
            for j in range(1,n):
                dp[j] = dp[j] + dp[j-1]
        return dp[-1]

官方技巧:移动到 (m, n) 总共需要 m+n-2 步,其中必有 m-1 步向下移动,n-1 步向左移动,故总路径为组合数:C(m+n-2)(m-1)

 64 最小路径和

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明:每次只能向下或者向右移动一步。

分析:dp[i][j] 代表走到 (i, j) 的数字总和

递推规律:dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + nums[i][j]

初始条件:dp[0][j] = sum(nums[0][:j])   dp[i][0] = sum(nums[:i][0])

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        dp = [[0]*n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if i==0:dp[i][j]=dp[i][j-1]+grid[i][j] 
                elif j==0:dp[i][j]=dp[i-1][j]+grid[i][j] 
                else:dp[i][j] = min(dp[i-1][j], dp[i][j-1])+grid[i][j]
        return dp[-1][-1]

# 这里有个trick,因为要处理0行0列,所以初始化必须得是0
# 因为处理0行0列时-1行-1列还没处理,元素均为0,不会对累加产生影响
 5 最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

方法一:二维动态规划

分析:dp[i][j] 代表 s[i:j] 是否为回文子串的情况

递推规律:dp[i][j] = dp[i+1][j-1] + (s[i]==s[j])

初始条件:i=j时 dp[i][j] = true

需要记录最长长度和起始位置;注意dp的!!!更新方向!!!

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        dp = [[False]*length for _ in range(length)]
        
        start, maxlen, length = 0, 0, len(s)

        for i in range(length-1,-1,-1):
            for j in range(i,length):
                if j==i:dp[i][j] = True
                elif j==i+1:
                    if s[i]==s[j]:
                         dp[i][j] = True
                else:
                    if dp[i+1][j-1] and s[i]==s[j]:
                        dp[i][j] = True

                if dp[i][j]:
                    maxlen = max(maxlen, j-i+1)
                    if maxlen == j-i+1:
                        start = i
        return s[start:start+maxlen]
    # 问题出在需要用dp[i+1][j-1]决定dp[i][j]的状态,所以需要先更新dp的左下方(i需要倒序)

方法二:中心扩散法

回文子串的有1or2个中心;

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        out = ''
        for i in range(len(s)):
            sub1 = self.palindrome(s, i, i)
            sub2 = self.palindrome(s, i, i+1)
            out = sub1 if len(sub1) > len(out) else out
            out = sub2 if len(sub2) > len(out) else out
        return out

    def palindrome(self, s, l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l+1:r]

相同时间复杂度的情况下,方法二比方法一节省了内存开销;

减小时间复杂度:马拉车算法...

 1143 最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

分析:dp[i][j] 代表 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度

递推规律:当text1[i] = text2[j]时,dp[i][j] = dp[i-1][j-1]+1  

                  当text1[i] != text2[j]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])  

初始条件:dp[0][:]=0    dp[:][0]=0

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[-1][-1]
 72 编辑距离

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。你可以进行插入/删除/替换三种操作;

分析:dp[i][j] 代表 word1[0:i] 转换成 word2[0:j] 使用的最少操作数;

递推规律:当 word1[i-1] = word2[j-1] 时,dp[i][j] = dp[i-1][j-1]

                  当 word1[i-1] != word2[j-1] 时,dp[i][j] = min(增/删/改)+1

                        增:word[i-1][j]  删:word[i+1][j]  改:word[i-1][j-1] 但增/删会卡死i的遍历方向;

                        增加word1和删减word2的操作数等价:word1=smile      word2=smilea

                        增:word[i-1][j]  删:word[i][j-1]  改:word[i-1][j-1]

初始条件:dp[0][j]=j   dp[i][0]=i文章来源地址https://www.toymoban.com/news/detail-843625.html

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m, n = len(word1), len(word2)
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(m+1):
            for j in range(n+1):
                if i==0:dp[i][j] = j
                elif j==0:dp[i][j] = i 
                else:
                    if word1[i-1]==word2[j-1]:
                        dp[i][j] = dp[i-1][j-1]
                    else:
                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
        return dp[-1][-1]

到了这里,关于【Leetcode】top 100 多维动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode100-086到090】【动态规划】一维五题合集2

    【单词拆分】 给你一个字符串  s  和一个字符串列表  wordDict  作为字典。如果可以利用字典中出现的一个或多个单词拼接出  s  则返回  true 。 注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 思路: 首先,我们依次考虑s的前i个字母能否被

    2024年02月19日
    浏览(10)
  • 【Leetcode】top 100 图论

    基础知识补充 1.图分为有向图和无向图,有权图和无权图; 2.图的表示方法:邻接矩阵适合表示稠密图,邻接表适合表示稀疏图;    邻接矩阵:    邻接表: 基础操作补充 1.邻接矩阵: 2.邻接表: 3.图的遍历:  题目 200 岛屿数量 给你一个由  \\\'1\\\' (陆地)和  \\\'0\\\' (水)组

    2024年04月10日
    浏览(10)
  • Leetcode题解-算法-动态规划(python版)

    1.1 爬楼梯 70. 爬楼梯(Easy) 走n阶楼梯的方法有两种,1、先走 1 级台阶,再走 n-1 级台阶;2、先走 2 级台阶,再走 n-2 级台阶 f(n) = f(n-1) + f(n-2) 1.2 强盗抢劫 198. 打家劫舍(Medium) 每个房间财产为 nums[0]……nums[n-1]。 假设 0 至 x 间房获得的最大财产为 f(x)。 f(x) = max(f(x-1),f(x-2)+nums[

    2024年02月03日
    浏览(13)
  • LeetCode - #85 最大矩形(Top 100)

    本题为 LeetCode 前 100 高频题 本题由于没有合适答案为以往遗留问题,最近有时间将以往遗留问题一一完善。 我们社区陆续会将顾毅( Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。 )的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 LeetCode 算法到目前我

    2024年02月10日
    浏览(10)
  • LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    题目链接:343. 整数拆分 题目描述: 给定一个正整数  n  ,将其拆分为  k  个  正整数  的和(  k = 2  ),并使这些整数的乘积最大化。 返回  你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 算法分析: 定义dp数组及下标含义: dp[i]表述正整数i拆分成k个正整数

    2024年02月04日
    浏览(6)
  • 算法练习Day30 (Leetcode/Python-动态规划)

    62. Unique Paths There is a robot on an  m x n  grid. The robot is initially located at the  top-left corner  (i.e.,  grid[0][0] ). The robot tries to move to the  bottom-right corner  (i.e.,  grid[m - 1][n - 1] ). The robot can only move either down or right at any point in time. Given the two integers  m  and  n , return  the number of possible

    2024年01月20日
    浏览(10)
  • LeetCode算法题解(动态规划)|LeetCoed62. 不同路径、LeetCode63. 不同路径 II

    题目链接:62. 不同路径 题目描述: 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 示例 2:

    2024年02月05日
    浏览(12)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(14)
  • 【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月16日
    浏览(10)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包