leetcode刷题笔记 task2 动态规划

动态规划主要思想：

如果需要解决一个给定的问题，我们需要解决这个问题的子问题，再根据子问题的解得到原问题的解，可以考虑动态优化算法。动态优化往往适用于优化递归问题，减少重复运算的过程。
动态规划的步骤

确定动态规划状态
写出状态转移方程和状态转移表
考虑初始化条件
考虑输出状态
5.考虑时间和空间复杂度的优化

动态规划练习1

leetcode #5 最长回文子串
难度：中等
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
解决这道题容易想到需要通过遍历字符串s的每一个子串，判断其是否为回文序列，再记录所有为回文序列中最大的一个。其中，判断字符串是否为回文序列可以使用动态规划的思想：一个字符串s如果为回文序列，需要满足s[0]==s[-1]并且s[1:-2]也为回文序列。
写出状态转移方程：
用i, j表示某子串的首位下标，创建动态规划状态转移表dp
则dp[i][j] = True if s[i] == s[j] and dp[i+1][j-1] == True
初始化条件：
dp[i][j] = True if i==j, dp[i][j] = True if j == i + 1 and s[i] == s[j]
完整代码如下：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 0:
            return ''
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]        
        res = (0,(0,0)) #记录子串的长度以及子串首尾坐标结果
        for l in range(len(s)): # l表示子串的长度
            for i in range(len(s)):
                j = i + l
                if j > len(s)-1:
                    break
                if l == 0:
                    dp[i][j] = True
                elif l == 1:
                    if s[i] == s[j]:
                        dp[i][j] = True
                else:
                    if s[i] == s[j] and dp[i+1][j-1] == True:
                        dp[i][j] = True
                if dp[i][j] == True:
                    if l > res[0]:
                        res = (l,(i, j)) #更新结果
        i, j = res[1]
        return s[i:j+1]

动态规划练习2

leetcode #72 编辑距离
难度：困难
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

动态规划：
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以，
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
第一行，第一列要单独考虑:
第一行，是 word1 为空变成 word2 最少步数，就是插入操作；第一列，是 word2 为空，需要的最少步数，就是删除操作

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        # 第一行
        for j in range(1, n2 + 1):
            dp[0][j] = dp[0][j-1] + 1
        # 第一列
        for i in range(1, n1 + 1):
            dp[i][0] = dp[i-1][0] + 1
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] ) + 1
        return dp[-1][-1]

动态规划练习3

leetcode #198 打家劫舍
难度：简单
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

状态转移：小偷在沿街偷盗时要对是否进入每一家盗窃进行判断，判断的规则应该为：比较上上家为盗窃最后一家所得到的最大金额加上当前家，以及上一家为盗窃的最后一家所得到的最大金额（因为不能盗窃相邻的两家），两者取更大的一个作为选择，即：
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
初始化条件：
dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
输出：dp[-1]
代码如下：

lass Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0], nums[1])
        dp =  [nums[0], max(nums[0], nums[1])]
       
        i = 2
        while i <= len(nums)-1:
            dp.append(max(nums[i] + dp[i-2],dp[i-1]))
            i += 1
        return dp[-1]

动态规划练习4

leetcode #213 打家劫舍2
难度：中等
这道题是198的一个小升级，不能同时打劫第一家和最后一家，其实只需要把nums拆分为nums[0:-1]和nums[1:]再分别利用动态规划求解，最后比较两个结果大小即可代码如下：

class Solution(object):
    def dp(self,nums):
        if len(nums) ==1:
            return nums[0]
        elif len(nums) ==2:
            return max(nums[0], nums[1])
        dp = [0]*len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-2]+nums[i],dp[i-1])
        return dp[-1]
    
    def rob(self, nums):
        if len(nums) == 0:
            return 0
        elif len(nums) ==1:
            return nums[0]
        
        # 拆分数组
        # sub1 nums[0] to nums[N-2]
        # sub2 nums[1] to nums[N-1]
        sub1 = nums[0:-1]
        sub2 = nums[1:]
        
        return max(self.dp(sub1), self.dp(sub2))

动态规划练习5

leetcode #516 最长回文子序列
难度：中等
状态转移：
dp矩阵记录首尾坐标为i,j的子字符串中最长回文序列的长度
如果s[i] == s[j] 则dp[i][j]等于去掉首尾的子字符串的最长回文序列的长度
否则，dp[i][j] = max(dp[i][j-1], dp[i+1][j])
初始化：
如果子字符串长度为1，则其本身就是回文子序列，dp[i][i] = 1
代码如下：

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i+1][j])
        return dp[0][n-1]

动态规划练习6

leetcode #674 最长连续递增序列
难度：简单
给定一个未经排序的整数数组，找到最长且连续的的递增序列，并返回该序列的长度。
示例:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。

设dp[i][j]记录首尾下标为i，j的子序列是否为连续递增序列和该子序列的长度
状态转移：
dp[i][j][0] = True if nums[j] > nums[j-1] and dp[i][j-1][0] == True else False
考虑优化时间空间复杂度，用变量count记录当前序列连续递增的元素个数，一旦不满足连续递增则count变回1，再利用变量res在遍历每个元素的时候记录count所达到的最大值。
这样时间复杂度降为O(n)，空间复杂度降为O(1)
代码如下：

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return 1
        count = 1
        res = 1
        for i in range(1,len(nums)):
            if nums[i] > nums[i-1]:
                count += 1
            else:
                count = 1
            res = max(res, count)

        return res