leetcode 动态规划总结

算法
, ,

动态规划 Dynamic Programming 是分阶段求解问题，具有最优子结构、边界和状态转移公式三个要素。

一般来说，给定一个规则，让我们求任意状态下的解，都是用动态规划。

斐波那契数列

台阶问题

Leetcode : 70. Climbing Stairs (Easy)

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

问题描述：分解为子问题，F(n) = F(n-1) + F(n-2),是一个斐波那契数列，可以直接用递归求解，但递归的时间复杂度是指数级别的 o(n2) ，会出现参数被重复计算的问题。

利用动态规划求解：F(n-1) 和 F(n-2) 是 F(n) 的最优子结构，F(1) 和 F(2) 是问题边界（可以直接得出结果，不需要继续简化），F(n) = F(n-1) + F(n-2) 即状态转移公式。

自底向上对该问题进行求解，由于 F(n) 只依赖于 F(n-1) 和 F(n-2)，因此可以使用中间变量将其进行保存，从 1-n 依次迭代。此时时间复杂度为 o(n),空间复杂度为 o(1)

1
2
3
4
5
6
7
8
9
def climb_stairs(n):
    a = b = 1
    if n == 1:
        return 1
    for i in range(1,n):
        cur = a + b
        a = b
        b = cur
    return cur

备注：

  1. python 中无需关心其实际含义的变量可用 _ 代替，仅需要循环，不需要计数
  2. a 表示到 i-2 台阶的方法数，b 表示到 i-1 台阶的方法数，cur 表示到当前台阶的方法数

爬楼梯的最低成本

Leetcode : 746. Min Cost Climbing Stairs (Easy)

问题描述：爬楼梯，每次可以走一层或者两层，每层都有一个花费 cost[i]， 求到顶点时的最小花费。

方法一：
可以用一个列表 dp[i] 来表示到达第 i 层的花费(到达第 i 层时不需要加上 cost[i])，则我们要求的到顶点的花费即为 dp[len(cost)]， dp[] 的长度比 cost[] 的长度更大 1。
因此到达第 i 层时，可能是从 i-1 层跳上来，也可能是从 i-2 层跳上来，需要求这两种情况下的最小值。

该方法的时间复杂度为 o(n)，空间复杂度为 o(n)

1
2
3
4
5
def min_cost_climb_stairs(cost):
    dp = [0, 0]
    for i in range(2, len(cost)+1):
        dp.append(min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1]))
    return dp[len(cost)]

方法二：
由于 dp[i] 只与 dp[i-2] 和 dp[i-1] 以及 cost 有关，因此用三个变量即可。用 pre1 代表 dp[i-1]，用 pre2 代表 dp[i-2]， 用 cur 代表 dp[i]。
该方法的时间复杂度为 o(n)，空间复杂度为 o(1)

1
2
3
4
5
6
7
def min_cost_climb_stairs(cost):
    pre1, pre2 = 0, 0
    for i in range(2, len(cost) + 1):
        cur = min(pre2 + cost[i-2], pre1 + cost[i-1])
        pre2 = pre1
        pre1 = cur
    return cur

强盗抢劫房子

Leetcode : 198. House Robber (Easy)

问题描述：抢劫一排住户，不能抢相邻的，求最大的抢劫金额。与上一题相似。

抢劫到第 i 个住户时最大的抢劫量为 dp[i]，由于不能抢 i-1 的住户，因此此时只能抢 i-2 或 i-3 的住户，因此 dp[i] 依赖于 dp[i-2] 和 dp[i-3] 的值；

方法一：采用备忘录算法，该解法的时间复杂度为 o(n),空间复杂度为 o(n)，使用列表 dp[] 来记录下抢劫到第 i 个房子时最大的抢劫量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def rob(nums):
    size = len(nums)
    if size == 0:
        return 0
    if size == 1:
        return nums[0]
    if size == 2:
        return max(nums[0], nums[1])
    dp = []
    dp.append(nums[0])
    dp.append(max(nums[0], nums[1]))
    dp.append(max(nums[0]+nums[2], nums[1]))
    for i in range(3, size):
        dp.append(max(dp[i-2], dp[i-3]) + nums[i])
    return max(dp[size-1], dp[size-2])

方法二：改进算法，空间复杂度 o(1) 实现。由于 dp[i] 依赖于 dp[i-2] 和 dp[i-3] 的值，因此需要记录下这两个的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def rob(self, nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    if len(nums) == 2:
        return max(nums[0], nums[1])
    
    pre1 = max(nums[0], nums[1])
    pre2 = nums[0]
    for i in range(2, len(nums)):
        cur = max(pre1, pre2+nums[i])
        pre2 = pre1
        pre1 = cur
    return cur

强盗抢劫房子II

Leetcode : 213. House Robber II (Medium)

问题描述：房子的分布变为环形，即第一个和最后一个相邻，可以分别求去掉第一个的最大值，和去掉最后一个的最大值，然后比较两者的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rob(self, nums):
    size = len(nums)
    if not nums:
        return 0
    if len(nums) <= 3:
        return max(nums)
    return max(self.rob2(nums[1:]), self.rob2(nums[:size-1]))
    
def rob2(self, nums):
    pre1 = max(nums[0], nums[1])
    pre2 = nums[0]
    for i in range(2, len(nums)):
        cur = max(pre2+nums[i], pre1)
        pre2 = pre1
        pre1 = cur
    return cur

背包问题

0-1背包

0-1 背包问题是在 M 件物品取出若干件放在空间为 N 的背包里，每种物品有且只有一个，并且有体积 w 和价值 v 两个属性。

定义二维数组 dp 来存储最大价值，dp[i][j] 表示体积为 j 的背包，前 i 件物品能够达到的最大价值。对于第 i 件物品，有两种情况：

  1. 不放入第 i 件物品，则能够达到的最大价值为放入前 i-1 件物品的最大价值，即 dp[i][j] = dp[i-1][j]；
  2. 放入第 i 件物品，则能够达到的最大价值为放入前 i-1 件物品的最大价值加上第 i 件物品的价值，即 dp[i][j] = dp[i-1][j-w[i]] + v[i]。

选出上述两种情况下的最大价值，则为空间为 j 的背包能够放下的物品的最大价值。因此，可以得到状态转移方程为：


方法一：以填充格子的形式求解，返回最后一个格子即得到最大价值。
该方法的时间复杂度为 o(NM), 空间复杂度为 o(NM)

1
2
3
4
5
6
7
8
9
10
def bag_01(M, N, weights, values):
    dp = [[0 for j in range(N+1)] for i in range(M)] # 初始化二维数组，物品数 M 为行，背包容量 N 为列
    for j in range(N+1):
        dp[0][j] = values[0] if j >= weights[0] else 0 # 填充边界
    for i in range(1, M):
        for j in range(1, N+1):
            dp[i][j] = dp[i-1][j]
            if j >= weights[i]:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])
    return dp[M-1][N]

填完表格后，仅能得到最优解，但不知道最优解由哪些元素组成，通过最优解回溯，可以找到选择的物品。

  1. 当 dp[i][j] = dp[i-1][j] 时，说明第 i 件物品没有被选择， 则回到 dp[i-1][j]
  2. 当 dp[i][j] = dp[i-1][j-weights[i]] + values[i], 说明选择了第 i 件物品，然后再回到装该物品之前的状态，即 dp[i-1][j-weights[i]] 时
  3. 遍历到 i=0 时，找到组成最优解的商品 
1
2
3
4
5
6
7
8
def bag_res(dp, N, M, weights, values):
    j = N
    res = []
    for i in range(M-1, -1, -1):
        if dp[i][j] == dp[i-1][j-weights[i]] + values[i]:
            res.append(i+1)
            j = j - weights[i]
    return res

方法二：优化空间。由状态转移公式可知，前 i 件物品的状态只与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，用 dp[j] 来表示 dp[i][j] 和 dp[i-1][j]。此时的状态转移方程为：

此时时间复杂度为 o(M * N), 空间复杂度为 o(N)

需要注意的是：dp[] 填充时，必须要从右到左进行填充，也就是 j 应该倒序循环求解。否则，前一项的值即 dp[j-weights[i]] 改变了，dp[j] 无法求得正确的结果。

但使用该方法，由于之前的数据被覆盖掉，只能够得到最后的最大价值，无法知道最优解由哪些元素组成，两种方法各有利弊。

1
2
3
4
5
6
7
def bag01(M, N, weights, values):
    dp = [0]*(N+1)
    for i in range(0, M):
        for j in range(N, -1, -1):
            if dp[j] <= dp[j-weights[i]] + values[i] and j-weights[i] >= 0:
                dp[j] = dp[j-weights[i]] + values[i]
    return dp[N]

完全背包

与 0-1 背包的条件基本一致，但每种物品都有若干件。
思路：

  1. 用 dp[i][j] 表示前 i 种物品放入若干件时到空间为 j 的背包中的最大价值。
  2. 根据第 i 种物品放入的件数进行决策，对于空间 j，物品 i 能够放入的最大件数为 j/weights[i]，将其转化为 0-1背包求解。

转为转移公式为, k 表示件数，(0 <= k * weights[i] <= j)：

此时时间复杂度为 o(NM∑(j/weights[i]))

优化一：
直接对放与不放第 i 件物品进行决策。

  1. 不放第 i 件物品，则 dp[i][j] = dp[i-1][j]
  2. 放第 i 件物品，则 dp[i][j] 中至少会出现一件物品 i，我们认为之前已经最大限度地放置了物品 i，如果能够放进去就放最后一件 i， 则此时 dp[i][j] = dp[i][j-weights[i]] + values[i]， 注意此处与 0-1背包的区别。

此时的状态转移公式为：

优化二：
使用一维数组进行存储，状态转移公式与 01背包 的一维数组解法相同：

此时要注意的是，完全背包与 01背包 的一维数组解法的遍历顺序不同：
01背包遍历 j 时需要逆序遍历，使得 dp[j-weights[i]] 存储的值为 dp[i-1][j-weights[i]] 的值，每个物品只使用一次；
而完全背包遍历 j 时需要正序遍历，此时 dp[j-weights[i]] 存储的值为 dp[i][j-weights[i]]的值，每个物品可以使用多次。

1
2
3
4
5
6
7
8
def complete_bag(M, N, weights, values):
    dp = [0] * (N + 1)
    for i in range(0, M):
        for j in range(weights[i], N+1): #1
            if dp[j] <= dp[j - weights[i]] + values[i] and j - weights[i] >= 0:
                dp[j] = dp[j - weights[i]] + values[i]
        print(dp)
    return dp[N]

备注： 1. 唯一不同的地方在于对 j 的遍历。此处从 weights[i] 到 N+1

二维费用的背包

二维费用的背包是：对每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种费用。对每种费用都有一个可付出的最大值，即背包容量。

设第 i 件物品所需的两种费用分别为 weights1[i] 和 weights2[i], 两种费用可付出的最大值为 N1 和 N2，物品的价值为 values[i]。

由于费用增加一维，则此时状态转移公式也需要增加一维，变为 dp[i][j][k]，用来表示前 i 件物品付出两种费用为 j 和 k 时可以获得的最大价值。此时的状态转移公式为：

优化空间，使用二维形式表示：

时间复杂度为 o(N1N2M), 空间复杂度为 o(N1N2)

注意：

  1. 若每件物品只能取 1 次，即 01背包，则变量 j,k 逆序循环。
  2. 若每件物品可以取多次，即完全背包，则变量 j,k 顺序循环。

背包问题练习

按单词列表分割字符串

Leetcode : 139. Word Break (Medium)

问题描述：按照单词列表来分割字符串，若是分隔的字符串都在 word_dict 中，则返回 True。

用 dp[i] 来表示到第 i 个字符时是否可以被正确分割。对于上述的例子，有 dp[0] == True; dp[4] == True; dp[8] == True。当最后一个 dp[len(s)] == True 时，则表明整个字符串都可以被分割。

1
2
3
4
5
6
7
8
9
def word_break(s, word_dict):
    n = len(s)
    dp = [False for i in range(n+1)]
    dp[0] = True
    for i in range(1, n+1):
        for word in word_dict:
            if dp[i-len(word)] and s[i-len(word):i] == word:
                dp[i] = True
    return dp[n]

找零钱

Leetcode : 322. Coin Change (Medium)

思路：显然这是一个完全背包问题，不同的是要寻找最少的硬币数来组成总额 amount，因此可以用 dp[] 来表示最少的硬币数，dp[] 的初始化应为无穷大。

状态转移公式为：

1
2
3
4
5
6
7
8
def coin_change(coins, amount):
    INF = float("inf")  #1
    dp = [0] + [INF] * amount 
    for i in range(len(coins)):
        for j in range(coins[i], amount + 1):
            if dp[j - coins[i]] != INF:
                dp[j] = min(dp[j], dp[j - coins[i]] + 1) 
    return dp[amount] if dp[amount] != INF else -1

备注：1. 注意 python 中无穷大可以用 float(“inf”) 来表示， 也可以写成 INF = 0x7ffffffe

组合总和

Leetcode : 377. Combination Sum IV (Medium)

问题描述：组合 nums 中的数使它们的和为 target。

思路：用 dp[i] 表示 target 为 i 时，nums[] 可以组合的总数，那么对于上述的 dp[4]，遍历一遍 nums[], dp[4] = dp[3] + dp[2] + dp[1] （3，2，1三个数字），因此状态转移公式为：

1
2
3
4
5
6
7
def combinationSum4(nums, target):
    dp = [1] + [0] * target  #1
    for i in range(target + 1):
        for num in nums:
            if num <= i:
                dp[i] += dp[i - num]
    return dp[target]

备注：
1.这里 dp[0] = 1 是因为当正好 nums[] 中有数字能组成 i 时，比如 3 一个数字就可以组成 dp[3]，那么 dp[3] += dp[0]，有一种解法。
2. dp[i-num] 表示能组成 i-num 的解法数，在这些解法的末尾加入 num，则得到 dp[i] 的解法，遍历一遍nums，所有 dp[i] 的解法数相加则得到最终结果，不会产生重复和缺失的问题。

划分数组为和相等的两部分

Leetcode : 416. Partition Equal Subset Sum (Medium)

问题描述：将一个数组划分为和相等的两部分。可以看成是一个背包大小为 sum/2 的 0-1背包问题，且这个背包必须要被填满。可以用一个一维数组进行求解，将每个数字所占空间和价值都用 nums[i] 来表示。由题意得到的状态转移公式为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def can_partition(nums):
    if len(nums) <= 1:
        return False
    V = sum(nums) // 2
    if 2 * V != sum(nums):
        return False
    dp = [0] * (V + 1)
    for i in range(len(nums)):
        for j in range(V, -1, -1):
            if dp[j] <= dp[j - nums[i]] + nums[i] and j - nums[i] >= 0:
                dp[j] = dp[j - nums[i]] + nums[i]
                if dp[j] == V:
                    return True
    return False

用0-1组成最多的字符串

Leetcode : 474. Ones and Zeroes (Medium)

思路：该问题为二维费用的 01背包问题，有两个费用，0 的数量和 1 的数量，其为背包的最大容量。组成每一个 strs[i] 都需要花费一些 0 和 1，将每个 strs[i] 的价值看做 1。
时间复杂度为 o(mnl), 空间复杂度为 o(mn)

1
2
3
4
5
6
7
8
9
def find_max_form(strs, m, n):
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    for i in range(len(strs)):
        ones = strs[i].count('1')
        zeros = strs[i].count('0')
        for j in range(n, ones-1, -1):
            for k in range(m, zeros-1, -1):
                dp[j][k] = max(dp[j][k], dp[j - ones][k - zeros] + 1)
    return dp[n][m]

得到目标和

Leetcode : 494. Target Sum (Medium)

问题描述：给定一个数组 nums[] 和一个目标数字 s, 数组中的数可以是给定 + 或 -，求其和能组成 s 的方法的总数。

可以将 nums[]中的数看成两部分，要给 + 的数字为放入数组 P 中，要给 - 的数字放入数组 N 中，因此可以得到：

sum(P) - sum(N) = target
sum(p) + sum(N) = sum(nums)

由上式可以得到 sum(p) = (target + sum(nums)) // 2
因此该问题可以看成一个 0-1背包问题，从给定的 nums[] 中选出一个子集，如果其和等于 (target + sum(nums)) // 2, 则这个子集符合题意，找到有多少个这样的自己即得到所有的方法。

因此可以用 dp[i][j] 表示前 i 个数的和为 j 的方法总数。第 i 个数可以选择放入背包或者不放入，则状态转移公式为：

空间优化后的状态转移公式为：

时间复杂度为 o(n2), 空间复杂度为 o(n)

1
2
3
4
5
6
7
8
9
10
11
def find_target_sum_ways(nums, S):
    nsum = sum(nums)
    target = (nsum + S) // 2
    if nsum < S or (nsum + S) % 2 == 1:
        return 0
    dp = [0] * (target + 1)
    dp[0] = 1
    for i in range(len(nums)):
        for j in range(target, nums[i] - 1, -1): #1
            dp[j] = dp[j] + dp[j - nums[i]]
    return dp[target]

备注：1.此处的遍历从 target 到 num[i]-1，从而减少遍历的次数， 需要注意的是 range 的区间为左闭右开，即 [traget, nums[i]-1)

分割整数

解码方法

Leetcode : 91. Decode Ways (Medium)

问题描述：按照编码规则来将信息中的字母编码，给定编码，返回解码的方法总数。

思路：用 dp[i] 来表示前 i 个字符的解码总数，由于数字只有处于 1-26 之间时才可以解码，因此可以分为三种情况。

  1. dp[i] = dp[i-2] + dp[i-1], (10 < int(s[i-2 : i]) <= 26 and int(s[i-2 : i]) != 20)
  2. dp[i] = dp[i-2], (int(s[i-2 : i]) == 20 or int(s[i-2 : i]) == 10)
  3. dp[i] = dp[i-1], (s[i-1] != ‘0’)

必须要注意的时，0 只有和 10，20 才可以解码成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def numDecodings(self, s):
    size = len(s)
    if size == 0 or s[0] == '0': #1
        return 0
    dp = [1,1] + [0] * (size - 1)
    
    for i in range(2, size + 1):
        if 10 < int(s[i-2 : i]) <= 26 and int(s[i-2 : i]) != 20:
            dp[i] = dp[i-2] + dp[i-1]
        elif int(s[i-2 : i]) == 20 or int(s[i-2 : i]) == 10:
            dp[i] = dp[i-2]
        elif s[i-1] != '0':
            dp[i] = dp[i-1]
        else:
            return 0
    return dp[size]

备注：1. 必须先判断 size，再判断 s[0]，否则空字符串会造成数组越界。

完全平方数

Leetcode : 279. Perfect Squares(Medium)

问题描述：按完全平方数来分割整数，将一个数 n 分割成 1,4,9,16…… 的和。

思路：用 dp[i] 来存储组成数字 i 的完全平方数的最小个数，
因为：13 = 1 * 1 + 12， 13 = 2 * 2 + 9，13 = 3 * 3 + 4
那么 dp[13] = min(1 + dp[12], 1 + dp[9], 1 + dp[4])
状态转移公式为：

1
2
3
4
5
6
7
8
def num_squares(n):
    INF = float("inf")
    dp = [INF] * (n+1)
    dp[0] = 0
    for i in range(1, n+1):
        for j in range(1, int(math.sqrt(n)) + 1):
            dp[i] = min(dp[i], dp[i - j * j] + 1) 
    return dp[n]

数组区间

子数组最大和

Leetcode : 53. Maximum Subarray (Easy)

问题描述：找到一个数组中的连续子数组的最大的和。

到第 i 个数时的子数组最大和只可能是 sum[i-1] + nums[i] 或者是 nums[i]自身， 即
sum[i] = max(sum[i-1] + nums[i], nums[i])
当前 i-1 项的和 sum[i-1] <= 0 时，则 sum[i]
= nums[i]， 抛弃之前的子数组，从 i 开始寻找新的最大和的子数组。这样就可以得到每一部分的最大的 sum，最后再从每一部分的最大 sum 中找到整个数组的 max_sum 。 

1
2
3
4
5
6
7
8
9
def max_subArray(nums):
    if len(nums) == 0:
        return 0
    sum = 0
    max_sum = nums[0]
    for i in range(len(nums)):
        sum = max(sum + nums[i], nums[i])
        max_sum = max(max_sum, sum)
    return max_sum

Maximum Product Subarray

Leetcode : 152. Maximum Product Subarray (Medium)

思路： max[i] 表示以 i 结尾的子数组中的最大乘积，若要 O(1) 的空间复杂度，则用 res 记录下 max[i] 中的最大值。
但是由于会出现 负负得正 的情况，因此还需要记录下最小值 min[i]。
最大最小乘积只会在 [max[i-1] * nums[i], min[i-1] * nums[i], nums[i]] 三者之间产生。

1
2
3
4
5
6
7
8
def maxProduct(self, nums):
    res = maxp = minp = nums[0]
    for i in range(1, len(nums)):
        lastmax = maxp
        maxp = max(minp*nums[i], lastmax*nums[i], nums[i])
        minp = min(minp*nums[i], lastmax*nums[i], nums[i])
        res = max(res, maxp)
    return res

数组区间和

Leetcode : 303. Range Sum Query - Immutable (Easy)

1
2
3
4
5
6
7
8
class NumArray:
    def __init__(self, nums):
        self.dp = nums
        for x in range(1, len(nums)):
            self.dp[x] = self.dp[x-1] + nums[x]
        
    def sum_range(self, i, j):
        return self.dp[j] - self.dp[i-1] if i !=0 else self.dp[j]

备注：必须将前 x 个数的和先存下来，否则会超时；直接令 dp = nums，这样就不用再初始化 dp[0] = nums[0]，简洁高效。

最长递增子序列

子序列：已知一个序列 {S1, S2,…,Sn} ，取出若干数组成新的序列 {Si1, Si2,…, Sim}，其中 i1、i2 … im 保持递增，即新序列中各个数仍然保持原数列中的先后顺序，称新序列为原序列的一个子序列。

递增子序列：如果在子序列中，当下标 ix > iy 时，Six > Siy，称子序列为原序列的一个递增子序列。

最长递增子序列

Leetcode : 300. Longest Increasing Subsequence (Medium)

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

思路：定义数组 dp[i] 表示到第 i 个数的最长递增子序列的长度，则对于一个递增子序列 {Si1, Si2,…,Sim}，如果 im < n 并且 Sim < Sn ，此时 {Si1, Si2,…, Sim, Sn} 为一个递增子序列，递增子序列的长度增加 1。满足上述条件的递增子序列中，长度最长的即是最长递增子序列。
因此，状态转移公式为：


对于长度为 n 的序列，最长递增子序列不一定是以 nums[n-1] 结尾，因此 dp[n-1] 不一定是最长递增子序列的长度，应该是 dp[] 数组的最大值。

该解法的时间复杂度为 o(n2)， 空间复杂度为 o(n)

1
2
3
4
5
6
7
8
9
10
11
12
def length_of_LIS(self, nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [0] * n
    for i in range(n):
        dp_max = 1
        for j in range(i):
            if nums[i] > nums[j]:
                dp_max = max(dp_max, dp[j] + 1)
        dp[i] = dp_max
    return max(dp)

时间优化：利用二分查找可将时间复杂度优化到 o(nlogn)

最长公共子序列

最长回文子串

Longest Palindromic Substring

Leetcode : 5. Longest Palindromic Substring (Medium)

思路：枚举每个回文串的中点，再向左右两边扩展扫描，直到不是回文串为止，存在两种情况。

  • 回文串长度为奇数，则中点是 s 中的每个字符，有 len(s) 种可能
  • 回文串长度为偶数，则中点是 s[i]+s[i+1]，有 len(s)-1 种可能
    对于每个中心往两边扫的时间复杂度为 O(n)，则该方法的时间复杂度为 O((2n-1) * n) = O(n2)

以上思路需要对 s 遍历两边，对其进行改进，逐一遍历 s 中的每一个字符，并比较其与后面一个字符，如果相等的话，则先找到这一对相邻的字符，再向左右扩展，此时把 i 更新为 right 的值，这样也省去了一些重复的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestPalindrome(self, s):
    n = len(s)
    if n <= 1:
        return s
    res = ''
    for i in range(n):
        left = right = i
        while right < n-1 and s[right] == s[right+1]:
            right += 1
        i = right
        while left > 0 and right < n-1 and s[left-1] == s[right+1]:
            left -= 1
            right += 1
        if right-left+1 > len(res):
            res = s[left:right+1]
    return res

矩阵路径

Unique Paths

Leetcode : 62. Unique Paths (Medium)

一开始想将 dp 数组全部置为 0， 然后把第一行和第一列置为 1，实际可以简化为全部置为1。

1
2
3
4
5
6
def uniquePaths(self, m, n):
    dp = [[1 for j in range(m)] for i in range(n)]
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[n-1][m-1]

Unique Paths II

Leetocde : 63. Unique Paths II (Medium)

在矩阵中设置障碍，用 0 和 1 来表示该格是否有障碍。
填充 dp 时需要注意，如果是第一行第一列中出现了障碍，那么该障碍之后的路都走不通，需要全部置为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def uniquePathsWithObstacles(self, obstacleGrid):
    n = len(obstacleGrid)
    m = len(obstacleGrid[0])
    dp = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        if obstacleGrid[i][0] == 1:
            break
        dp[i][0] = 1
    for j in range(m):
        if obstacleGrid[0][j] == 1:
            break
        dp[0][j] = 1
    for i in range(1, n):
        for j in range(1, m):
            if obstacleGrid[i][j] != 1:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[n-1][m-1]

Minimum Path Sum

Leetcode : 64. Minimum Path Sum (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def minPathSum(self, grid):
    n = len(grid)
    m = len(grid[0])
    if n == 1 and m == 1:
        return grid[0][0]
    dp = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(m):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[n-1][m-1]

Triangle

Leetcode : 120. Triangle (Medium)

若要空间复杂度为 O(n)，则只能用一维数组，此时在遍历 j 的时候必须从后往前遍历，才不会丢失原来的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
def minimumTotal(self, triangle):
        n = len(triangle)
    dp = [0 for i in range(n)]
    dp[0] = triangle[0][0]
    for i in range(1, n):
        for j in range(i, -1, -1):
            if j == 0:
                dp[j] = dp[j] + triangle[i][j]
            elif j == i:
                dp[j] = dp[j-1] + triangle[i][j]
            else:
                dp[j] = min(dp[j], dp[j-1]) + triangle[i][j]
    return min(dp)

Dungeon Game

Leetcode : 174. Dungeon Game (Hard)
由题意，当其实的能量 HP <= 0 时则游戏结束，所以需要保证其实到每一个格子的时候，都有 HP >= 1。

思路：

  1. 从右下角向上填充格子，用 dp[i][j] 表示进入到 i,j 格子前需要的最小 HP 数，因此对于最后一个格子， dp[-1][-1] = max(1, -dungeon[-1][-1]+1)
  2. 在每一个格子 i,j ，骑士可能向下走或者向右走， 当 i=m-1 时，不能向下，只能向右走；当 j=n-1 时，只能向下走；当 i < m-1 and j < n-1 时，可能向下也可能向右，因此需要选择一条消耗能量最小的路径，dp[i][j] = min(down, right)
  3. 在每一个格子 i,j, 若骑士向下走，进入到 (i,j) 前需要的最少能量为 down = max(1, dp[i+1][j]-dungeon[i][j]); 若骑士向右走，进入到 (i,j) 前需要的最少能量为 right = max(1, dp[i][j+1]-dungeon[i][j])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def calculateMinimumHP(self, dungeon):
    m = len(dungeon)
    n = len(dungeon[0])
    dp = [[0 for j in range(n)] for i in range(m)]
    dp[-1][-1] = max(1, -dungeon[-1][-1]+1)
    
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            down = None
            if i < m-1:
                down = max(1, dp[i+1][j]-dungeon[i][j])
            right = None
            if j < n-1:
                right = max(1, dp[i][j+1]-dungeon[i][j])
            if down and right:
                dp[i][j] = min(down, right)
            elif down:
                dp[i][j] = down
            elif right:
                dp[i][j] = right
    return dp[0][0]

Maximal Square

Leetcode : 221. Maximal Square (Medium)

思路： 用 dp[i][j] 来存储以点 (i,j) 为右下角的正方形的最大边长。

  • 当 matrix[i][j] == ‘0’ 时，边长为 0，则 dp[i][j] = 0
  • 当 matrix[i][j] == ‘1’ 时，则比较 (i,j) 周围的三个点 (i-1,j) (i,j-1) (i-1,j-1) 取其最小值加一则为正方形边长。
    因此状态转移公式为： dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

最后要得到边长最大的正方形的面积，则用一个 res 记录下遍历时的最大边长即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maximalSquare(self, matrix):
    if not matrix:
        return 0
    n = len(matrix)
    m = len(matrix[0])
    dp = [[0 for j in range(m)] for i in range(n)]
    res = 0
    for i in range(n):
        dp[i][0] = int(matrix[i][0])
        res = max(res, dp[i][0])
    for j in range(m):
        dp[0][j] = int(matrix[0][j])
        res = max(res, dp[0][j])
    for i in range(1, n):
        for j in range(1, m):
            if matrix[i][j] == '1':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                res = max(res, dp[i][j])
            else:
                dp[i][j] = 0
    return res**2

其他

股票最大收益

Leetcode : 121. Best Time to Buy and Sell Stock (Easy)

问题描述：只能买入和卖出一次，求股票最大的收益。若是持续下跌，则收益为 0。
记录下最小值和最大的收益，遍历一遍，时间 o(n) 空间 o(1)

1
2
3
4
5
6
7
8
9
10
11
def max_profit(prices):
    if len(prices) == 0:
        return 0
    profit = 0
    pmin = prices[0]
    for i in range(len(prices)):
        if prices[i] < pmin:
            pmin = prices[i]
        if prices[i] - pmin > profit:
            profit = prices[i] - pmin
    return profit

Best Time to Buy and Sell Stock III

Leetcode : 123. Best Time to Buy and Sell Stock III (Hard)

问题描述：允许最多买入卖出 2 次，求最大 profit。

该题若将 prices 数组分为两个部分，再复用上题的结果分别计算每个部分的 maxProfit 会超时。

思路：考虑用两个数组来存储结果， profit_max1[i] 为前 i 天的最大利润，profit_max2[i] 为 i 天之后的最大利润，注意 profit_max2[i] 需要从后往前计算，而且存的是 pmax，用 pmax-prices[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maxProfit(self, prices):
    n = len(prices)
    if n <= 1:
        return 0
    profit_max1 = [0 for i in range(n)]
    profit_max2 = [0 for i in range(n)]
    
    pmin = prices[0]
    for i in range(1, n):
        profit_max1[i] = max(profit_max1[i-1], prices[i]-pmin)
        pmin = min(pmin, prices[i])
    
    pmax = prices[n-1]
    for i in range(n-2, -1, -1):
        profit_max2[i] = max(profit_max2[i+1], pmax-prices[i])
        pmax = max(pmax, prices[i])
        
    profit = 0
    for i in range(n):
        profit = max(profit, profit_max1[i]+profit_max2[i])
    return profit

Best Time to Buy and Sell Stock IV

Leetcode : 188. Best Time to Buy and Sell Stock IV (Hard)