LeetCode-动态规划

LeetCode91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        m = len(s)
        if m == 0 or s[0]=='0':
            return 0
        pre,cur = 0,1
        for i in range(1,m+1):
            if s[i-1] == '0':
                cur = 0
            if i<2 or not(s[i-2] == '1' or (s[i-2]=='2' and int(s[i-1])<=6)):
                pre = 0
            pre,cur = cur,pre+cur
        return cur

LeetCode152 乘积最大子序列

给定一个整数数组 nums， 找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n==0:return 0
        res =nums[0]
        max_res,min_res = 1,1
        for i in range(n):
            if nums[i]>0:
                max_res = max(max_res*nums[i],nums[i])
                min_res = min(min_res*nums[i],nums[i])
            elif nums[i]<0:
                max_res,min_res = max(min_res*nums[i],nums[i]),min(max_res*nums[i],nums[i])
            else:
                max_res,min_res = 0,0
            res = max(max_res,res)
        return res

LeetCode121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n== 0: return 0
        
        res = 0
        min_p= prices[0]
        for i in range(n):
            res = max(res,prices[i]-min_p)
            if min_p>prices[i]:
                min_p = prices[i]
        return res

LeetCode122. 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        res = 0
        for i in range(1,len(prices)):
            diff = prices[i] - prices[i-1]
            if diff>0:
                res += diff
        return res

LeetCode123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

---

f[i]表示[0:i]天交易的最大利润
g[i]表示[i:n-1]天交易的最大利润

---

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n<2: return 0
        f,g = [0]*n,[0]*n
        valley = prices[0]
        for i in range(1,n):
            valley = min(valley,prices[i])
            f[i] = max(f[i-1],prices[i]-valley)
        peak = prices[n-1]
        for i in range(n-2,-1,-1):
            peak = max(peak,prices[i])
            g[i] = max(g[i+1],peak-prices[i])
        res = 0
        for i in range(n):
            res = max(res,f[i]+g[i])
        return res

LeetCode714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。

---

sold[i]:表示第i天卖出股票所能获得的最大利润，那么，它的值应该等于前一天手里有股票时所拥有的最大利润加上今天卖出时获得的利润，和前一天手里没有保留股票，而是卖出股票时有的最大利润的较大者
hold[i]:表示第i天保留股票时所能获得的最大利润，它的值为前一天卖出了股票所拥有的最大利润减去今天买进股票的价格，和前一天保留了股票的较大者。

sold[i] = max(sold[i-1],hold[i-1]+prices[i]-fee)
hold[i] = max(sold[i-1]-prices[i],hold[i-1])

---

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        n = len(prices)
        sold,hold = [0]*n,[0]*n
        hold[0] = -prices[0]
        for i in range(1,n):
            sold[i] = max(hold[i-1]+prices[i]-fee,sold[i-1])
            hold[i] = max(sold[i-1]-prices[i],hold[i-1])
        return sold[n-1]

LeetCode132. 分割回文串 II

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。

lass Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        f = [n-i-1 for i in range(n+1)]
        p = [[0]*n for i in range(n)]
        # p[n-1][n]
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if s[i] == s[j] and(j-i<=1 or p[i+1][j-1] ==1):
                    p[i][j] = 1
                    f[i] = min(f[i],1+f[j+1])
        return f[0]

LeetCode139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        f = [False]*(n+1)
        f[0] = True
        for i in range(n+1):
            for j in range(i):
                f[i] = f[i] or (f[j] and s[j:i] in wordDict)
        return f[n]

LeetCode338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

---

dp[i] = dp[i-cycle]+1,其中cycle=0,2,4,8,16…，
比如，3的二进制：11，此时cycle为2，dp[3] = dp[3-2]+1

---

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        dp = [0]*(num+1)
        if num==0:return dp
        dp[1] = 1
        for i in range(2,num+1):
            if i == 2**dp[i-1]:
                cycle = i
            dp[i] = dp[i-cycle]+1
        return dp

#LeetCode368. 最大整除子集

给出一个由无重复的正整数组成的集合, 找出其中最大的整除子集, 子集中任意一对 (Si, Sj) 都要满足: Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        dp = [0]*n
        parent = [0]*n
        mx,mx_idx = 0,0
        nums = sorted(nums)
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if nums[j]%nums[i]==0 and dp[i]<dp[j]+1:
                    dp[i] = dp[j]+1
                    parent[i] = j
                    if mx<dp[i]:
                        mx = dp[i]
                        mx_idx = i
        res = []
        for i in range(mx):
            res.append(nums[mx_idx])
            mx_idx = parent[mx_idx]
        return res

LeetCode72. 编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

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 i in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for i in range(n+1):
            dp[0][i] = i
        for i in range(1,m+1):
            for j in range(1,n+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j] = dp[i-1][j-1] 
                else:
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
        return dp[m][n]

LeetCode97. 交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        m,n = len(s1),len(s2)
        if m+n != len(s3): return False
        l = [[False]*(n+1) for i in range(m+1)]
        l[0][0] = True
        for i in range(m):
            if s1[i]==s3[i] and l[i][0]:
                l[i+1][0] = True
        for i in range(n):
            if s2[i]==s3[i] and l[0][i]:
                l[0][i+1] = True
        for i in range(m):
            for j in range(n):
                l[i+1][j+1] = (s1[i]==s3[i+j+1] and l[i][j+1]) or (s2[j] == s3[i+j+1] and l[i+1][j])
                
        return l[m][n]