Butterfly

动态规划字符串 最长回文子序列 难度：中等 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。示例 1：输入：s = “bbbab”输出：4解释：一个可能的最长回文子序列为 “bbbb” 示例 2：输入：s = “cbbd”输出：2解释：一个可能的最长回文子序列为 “bb” 。 方法一 12345678910111213class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n-1,-1,-1): dp[i][i] = 1 for j in range(i+1,n): if s[i]==s[j]: dp[i][j] = dp[i+1][j-1]+2 ...

动态规划矩阵 不同路径II 难度：中等 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。 返回机器人能够到达右下角的不同路径数量。 测试用例保证答案小于等于 2 109。*示例 1：输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]输出：2解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径： 向右 -> 向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 -> 向右 示例 2：输入：obstacleGrid = [[0,1],[0,0]]输出：1 方法一 1234567891011121314151617181920class Solution(object): def uniquePathsWithObsta ...

动态规划字符串 最长回文子串 难度：中等 给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = “babad”输出：”bab”解释：”aba” 同样是符合题意的答案。 示例 2：输入：s = “cbbd”输出：”bb” 方法一 123456789101112131415161718192021222324class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ n = len(s) maxlen=1 be=0 def ishw(s,i,j): while(i<j): if s[i]!=s[j]: return False i+=1 j-=1 return ...

动态规划矩阵 三角形最小路径和 难度：中等 给定一个三角形 triangle ，找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。 示例 1：输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]输出：11解释：如下面简图所示： 2 3 4 6 5 74 1 8 3自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 示例 2：输入：triangle = [[-10]]输出：-10 方法一 1234567891011121314151617class Solution(object): def minimumTotal(self, triangle): """ :type triangle: List[List[int]] :rtype: int ...

动态规划字符串 两个字符串最小的ASCII删除和 难度：中等 给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和。 示例 1：输入: s1 = “sea”, s2 = “eat”输出: 231解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。在 “eat” 中删除 “t” 并将 116 加入总和。结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。 示例 2：输入: s1 = “delete”, s2 = “leet”输出: 403解释: 在 “delete” 中删除 “dee” 字符串变成 “let”，将 100[d]+101[e]+101[e] 加入总和。在 “leet” 中删除 “e” 将 101[e] 加入总和。结束时，两个字符串都等于 “let”，结果即为 100+101+101+101 = 403 。如果改为将两个字符串转换为 “lee” 或 “eet”，我们会得到 433 或 417 的结果，比答案更大。 方法一 12345678910111213141516class ...

动态规划字符串 编辑距离 难度：中等 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符 示例 1：输入：word1 = “horse”, word2 = “ros”输出：3解释：horse -> rorse (将 ‘h’ 替换为 ‘r’)rorse -> rose (删除 ‘r’)rose -> ros (删除 ‘e’) 示例 2：输入：word1 = “intention”, word2 = “execution”输出：5解释：intention -> inention (删除 ‘t’)inention -> enention (将 ‘i’ 替换为 ‘e’)enention -> exention (将 ‘n’ 替换为 ‘x’)exention -> exection (将 ‘n’ 替换为 ‘c’)exection -> execution (插入 ‘u’) 方法一 12345678910111213 ...

动态规划字符串 单词拆分 难度：中等 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。示例 1：输入: s = “leetcode”, wordDict = [“leet”, “code”]输出: true解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。 示例 2：输入: s = “applepenapple”, wordDict = [“apple”, “pen”]输出: true解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 示例 3：输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]输出: false 方法一 1234567891011121314class Solution: def wordBreak(self, s: str, wordDict: List[str]) - ...

动态规划矩阵 下降路径最小和 难度：中等 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。示例 1：输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]输出：13 示例 2：输入：matrix = [[-19,57],[-40,-5]]输出：-59 方法一 12345678910111213141516171819class Solution(object): def minFallingPathSum(self, matrix): """ :type matrix: List[List[int]] ...

动态规划矩阵 不同路径 难度：中等 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？示例 1：输入：m = 3, n = 7输出：28示例 2：输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。 向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 向下 -> 向右 -> 向下示例 3：输入：m = 7, n = 3输出：28示例 4：输入：m = 3, n = 3输出：6 方法一 123456789101112class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ ...

动态规划斐波那契类型 爬楼梯 难度：简单 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：输入：n = 2输出：2解释：有两种方法可以爬到楼顶。 1 阶 + 1 阶 2 阶 示例 2：输入：n = 3输出：3解释：有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 方法一1234567891011class Solution(object): def climbStairs(self, n): if n<=2: return n a = 1 b = 2 for i in range (2,n): tem = a a = b b = b +tem return b 解析我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子： f(x)=f(x−1)+f( ...