动态规划总结

Leetcode-213 打家劫舍2
【你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。】

class Solution:
    def rob(self, nums: [int]) -> int:
        def my_rob(nums):
            cur, pre = 0, 0
            for num in nums:
                cur, pre = max(pre + num, cur), cur
            return cur
        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) != 1 else nums[0]

1
2
3
4
5
6
7
8
9

Leetcode-322 零钱兑换
【给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。】

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1 


1
2
3
4
5
6
7
8
9
10
11

把数字翻译成字符串

【有一种将字母编码成数字的方式：‘a’->1, ‘b->2’, … , ‘z->26’。
我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。
由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个 ‘a’ 也可以看做是一个 ‘k’ 。但 10 只可能是 ‘j’ ，因为 0 不能编译成任何结果。现在给一串数字，返回有多少种可能的译码结果】

class Solution:
    def solve(self , nums: str) -> int:
        # write code here
        
        if len(nums) == 0:
            return 0
        
        dp = [0] * (len(nums) + 1)
        dp[0] = 1
        
        for i in range(len(nums)):
            
            if nums[i] != '0':
                dp[i+1] += dp[i]
                
            if i > 0 and nums[i-1] != '0' and int(nums[i-1:i+1]) <= 26:
                dp[i+1] += dp[i-1]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

数字字符串转化成ip地址
【现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
例如：
给出的字符串为"25525522135",
返回[“255.255.22.135”, “255.255.221.35”]. (顺序没有关系)

数据范围：字符串长度 0 \le n \le 120≤n≤12
要求：空间复杂度 O(n!)O(n!),时间复杂度 O(n!)O(n!)

注意：ip地址是由四段数字组成的数字序列，格式如 “x.x.x.x”，其中 x 的范围应当是 [0,255]。
】

#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s ):
        # write code here
        if len(s) < 4 or len(s) > 12: return []
        res, tmp = [], []
        def backtrack(idx):
            if len(tmp) == 4 and idx == len(s):
                res.append('.'.join(tmp))
            for i in range(1, 4):
                if idx+i > len(s): continue
                sub = s[idx:idx+i]
                if len(sub) > 1 and sub[0] == '0': continue
                if int(sub) > 255: continue
                tmp.append(sub)
                backtrack(idx+i)
                tmp.pop()
        backtrack(0)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

编辑距离

【给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作：1.插入一个字符2.删除一个字符3.修改一个字符。】

class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        n1 = len(str1)
        n2 = len(str2)
        #dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离
        dp = [[0] * (n2 + 1) for i in range(n1 + 1)] 
        #初始化边界
        for i in range(1, n1 + 1): 
            dp[i][0] = dp[i - 1][0] + 1
        for i in range(1, n2 + 1):
            dp[0][i] = dp[0][i - 1] + 1
        #遍历第一个字符串的每个位置
        for i in range(1, n1 + 1): 
            #对应第二个字符串每个位置
            for j in range(1, n2 + 1): 
                #若是字符相同，此处不用编辑
                if str1[i - 1] == str2[j - 1]: 
                    #直接等于二者前一个的距离
                    dp[i][j] = dp[i - 1][j - 1] 
                else:
                    #选取最小的距离加上此处编辑距离1
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 
        return dp[n1][n2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最长的括号子串
【给出一个长度为 n 的，仅包含字符 ‘(’ 和 ‘)’ 的字符串，计算最长的格式正确的括号子串的长度。

例1: 对于字符串 “(()” 来说，最长的格式正确的子串是 “()” ，长度为 2 .
例2：对于字符串 “)()())” , 来说, 最长的格式正确的子串是 “()()” ，长度为 4 .
】

class Solution:
    def longestValidParentheses(self , s: str) -> int:
        res = 0
        #记录上一次连续括号结束的位置
        start = -1 
        st = []
        for i in range(len(s)):
            #左括号入栈
            if s[i] == '(': 
                st.append(i)
            #右括号
            else: 
                #如果右括号时栈为空，不合法，设置为结束位置
                if len(st) == 0: 
                    start = i
                else:
                    #弹出左括号
                    st.pop()
                    #栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if len(st) != 0: 
                        res = max(res, i - st[-1])
                    #栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                    else: 
                        res = max(res, i - start)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

买卖股票的最好时机（二）
【假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费】

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        n = len(prices)
        #dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        dp = [[0] * 2 for i in range(n)] 
        #第一天不持股，总收益为0
        dp[0][0] = 0 
        #第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0] 
        #遍历后续每天，状态转移
        for i in range(1, n): 
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        #最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

买卖股票的最好时机（三）

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        n = len(prices)
        #初始化dp为最小
        dp = [[-10000] * 5 for i in range(n)] 
        #第0天不持有状态
        dp[0][0] = 0 
        #第0天持有股票
        dp[0][1] = -prices[0] 
        #状态转移
        for i in range(1, n): 
            dp[i][0] = dp[i - 1][0]
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
        #选取最大值，可以只操作一次
        return max(dp[n - 1][2], max(0, dp[n - 1][4])) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

309. 最佳买卖股票时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        n = len(prices)
        f0, f1, f2 = -prices[0], 0, 0
        for i in range(1, n):
            newf0 = max(f0, f2 - prices[i])
            newf1 = f0 + prices[i]
            newf2 = max(f1, f2)
            f0, f1, f2 = newf0, newf1, newf2
        
        return max(f1, f2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

97. 交错字符串
【给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味着字符串 a 和 b 连接。
】

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        m = len(s1)
        n = len(s2)

        if m+n != len(s3):
            return False

        dp = [[False]*(n+1) for _ in range(m+1)]

        for i in range(m+1):
            for j in range(n+1):
                if i == 0 and j != 0:dp[0][j] = dp[0][j-1] and s2[j-1]==s3[j-1]
                elif j == 0 and i != 0:dp[i][0] = dp[i-1][0] and s1[i-1]==s3[i-1]
                elif i == 0 and j == 0:dp[i][j] = True
                else:
                    dp[i][j] = (dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1]==s3[i+j-1])

        return dp[-1][-1]


        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

787. K 站中转内最便宜的航班
【有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。】

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:

        pre = [float("inf")] * n
        pre[src] = 0
        for _ in range(k + 1):
            cur = pre[:]
            for i, j, p in flights:
                if pre[i] + p < cur[j]:
                    cur[j] = pre[i] + p
            pre = cur[:]
        return pre[dst] if pre[dst] < float("inf") else -1

1
2
3
4
5
6
7
8
9
10
11
12
13