动态规划
1. lc 42 - 接雨水
- 题目来源
- 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
- 难度：困难
解题思路
对于每一列，我们都求它左边最高的墙和右边最高的墙，当前墙距离他们之间的小值的差值被记录为dif。若为正值，当前墙储存水量为dif。
首先用两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。
对于 max_left我们其实可以这样求得状态转移方程：max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个大值，就是当前列左边最高的墙了。
对于 max_right我们可以这样求：max_right[i] = Max(max_right[i+1],height[i+1])
复杂度分析
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def trap(self, height: List[int]) -> int:
max_left, max_right = [0 for _ in range(len(height))], [0 for _ in range(len(height))]
water = 0
for i in range(1,len(height)):
max_left[i] = max(max_left[i-1],height[i-1])
for j in range(len(height)-2,-1,-1):
max_right[j] = max(max_right[j+1],height[j+1])
for k in range(1,len(height)-1):
dif = min(max_left[k],max_right[k]) - height[k]
if dif > 0:
water += dif
return water
|
优化
双指针法将空间复杂度可以降到O（n）
2. lc 72 - 编辑距离
- 题目来源
- 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
- 难度：困难
能简化为子问题的题，都一般有2种解法：自顶向下的递归 和 自底向上的动态规划
解题思路 - 动态规划
再看个递归解法
解题思路 - 递归
递归会超时，因为inserted的递归计算会包含全部的swapped递归计算。@functools.lru_cache(None)可以解决超时问题。
复杂度分析
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution:
def minDistance(self, word1: str, word2: str) -> int:
self.word1,self.word2 = word1, word2
return self.recursion(0,0)
import functools
@functools.lru_cache(None)
def recursion(self, i,j):
if len(self.word1)==i or len(self.word2)==j:
return len(self.word1)-i + len(self.word2)-j
if self.word1[i] == self.word2[j]:
return self.recursion(i+1,j+1)
else:
inserted = self.recursion(i,j+1)
deleted = self.recursion(i+1,j)
swaped = self.recursion(i+1,j+1)
return min(inserted,deleted,swaped)+1
|
