Comments (1)
Leetcode
70 Climbing Stairs
类型:DP基础题
Time Complexity O()
Space Complexity O()
这道题作为DP的启蒙题(拥有非常明显的重叠子结构),我在这详细的讲一讲LC大神们的答案是如何从一个毫无优化的做法,效率极低的递归解法,慢慢的进化到他们现在的答案,也给不会DP思路的同学补一补基础。
Top-Down
这道题自顶向下的思考:如果要爬到n
台阶,有两种可能性:
- 在
n-1
的台阶处爬一层台阶 - 在
n-2
的台阶处爬两层台阶
继续向下延伸思考,到达每一次层一共有几种方法
这个问题就变成了2个子问题:
- 到达
n-1
层台阶有几种方法 - 到达
n-2
层台阶有几种方法
之后对返回子问题之和即可。
具体可以看下图。
根据以上的思路得到下面的代码
Solution 1: Recursion (TLE)
class Solution(object):
def climbStairs(self, n):
if n == 1: return 1
if n == 2: return 2
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
TLE原因:
以上代码实现之所以会TLE,是因为递归的时候出现了很多次重复的运算。就如上图显示的爬n-2
层的计算出现了2次,这种重复计算随着input
的增大,会出现的越来越多,时间复杂度也会将以指数的级别上升。
优化思路:
这时候的思路为:如果能够将之前的计算好了的结果存起来,之后如果遇到重复计算直接调用结果,效率将会从之前的指数时间复杂度
,变成O(N)
的时间复杂度。
实现方法:
有了思路,实现方面则开辟一个长度为N的数组,将其中的值全部赋值成-1
,具体为什么要用-1
,是因为这一类问题一般都会要你求多少种可能,在现实生活中,基本不会要你去求负数种可能,所以这里-1
可以成为一个很好的递归条件/出口。
然后只要我们的数组任然满足arr[n] == -1
,说明我们在n
层的数没有被更新,换句话说就是我们还在向下递归或者等待返回值的过程中,所以我们继续递归直到n-1
和n-2
的值返回上来。这里注意我们递归的底层,也就是arr[0]和arr[1],我们要对起始条件进行初始化:arr[0], arr[1] = 1, 2
Solution 2: Top-Down (using array)
class Solution(object):
def climbStairs(self, n):
if n == 1: return 1
res = [-1 for i in range(n)]
res[0], res[1] = 1, 2
return self.dp(n-1, res)
def dp(self, n, res):
if res[n] == -1:
res[n] = self.dp(n - 1, res) + self.dp(n - 2, res)
return res[n]
这样是不是还是很抽象?我们可以举个例子,当n = 4
的时候,我们在每一层返回之前打印一下当前的数组的值:
# print(n+1, res)
(2, [1, 2, -1, -1])
(1, [1, 2, -1, -1])
(3, [1, 2, 3, -1])
(2, [1, 2, 3, -1])
(4, [1, 2, 3, 5])
大家看到了,我们先从第4
层开始递归,当递归到了1
和2
层的base case的时候,开始进行返回的计算,
当到了第3
层,将1
和2
层加起来,得到3
,继续返回
当到了第4
层,将2
和3
层加起来,得到了5
,这时候res[n] = 5,则满足出口条件,进行返回。
这就是Top-Down的思路,从大化小,思路就和DFS Tree中的分制一样。
Bottom-Up
Bottom-Up的思路则相反。我们不从n
层向下考虑,而是解决我们每一层向上的子问题。在每一层,我们其实只需要知道在当前节点,我们的n-1
和n-2
的值是多少即可。
当我们有了第1层和第2层的base case,我们则可以直接从base case向上推得第3层,第4层以及第n层的答案,具体实现如下:
Solution 3: Bottom-Up (using array)
class Solution(object):
def climbStairs(self, n):
if n == 1: return 1
res = [0 for i in range(n)]
res[0], res[1] = 1, 2
for i in range(2, n):
res[i] = res[i-1] + res[i-2]
return res[-1]
这种方法的使用的时候,我们发现其实在每一次更新当前的数的时候,我们最终返回的是最后一次更新的数,而我们的dependency
是n-1
和n-2
中的值,我们根本不需要一个数组去储存,直接用两个函数即可。所以底下为Bottom-Up的优化:
Solution 3: Bottom-Up (Constant Space)
class Solution(object):
def climbStairs(self, n):
if n == 1: return 1
a, b = 1, 2
for _ in range(2, n):
a, b = b, a + b
return b
198 House Robber
类型:DP基础题
Time Complexity O(N)
Space Complexity O(1)
class Solution(object):
def rob(self, nums):
if not nums: return 0
if len(nums) <= 2: return max(nums)
res = [0] * len(nums)
res[0], res[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
res[i] = max(res[i-1], res[i-2] + nums[i])
return res[-1]
以上的代码需要O(N)空间,利用滚动数组可以实现O(1)空间:
class Solution(object):
def rob(self, nums):
if not nums: return 0
if len(nums) <= 2: return max(nums)
res = [0] * 2
res[0], res[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
res[i%2] = max(res[(i-1)%2], res[(i-2)%2] + nums[i])
return max(res[0], res[1])
213. House Robber II
类型:DP基础题
Time Complexity O(N)
Space Complexity O(1)
这道题相对于House Robber I里面要解决的edge就是circle的头和尾不能为邻居,那我们只需要在之前写好的代码基础上计算两个区间即可,第一个区间是nums[1:], 第二个区间是nums[:-1],在比较这两个区间哪个大即可。
如上面的例图,对于[3, 10, 7]
这个数组,其实我们要做的就将其分成两个数组:
数组1: [3, 10]
,也就是 nums[:-1]
数组2: [10, 7]
, 也就是nums[1:]
然后用求出这两个区间中的最大值即可。
class Solution(object):
def rob(self, nums):
if not nums: return 0
if len(nums) <= 2: return max(nums)
return max(self.rob_row(nums[1:]), self.rob_row(nums[:-1]))
def rob_row(self, nums):
res = [0] * len(nums)
res[0], res[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
res[i] = max(res[i-1], res[i-2] + nums[i])
return res[-1]
滚动数组优化
class Solution(object):
def rob(self, nums):
if not nums: return 0
if len(nums) <= 2: return max(nums)
return max(self.rob_row(nums[1:]), self.rob_row(nums[:-1]))
def rob_row(self, nums):
res = [0] * 2
res[0], res[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
res[i%2] = max(res[(i-1)%2], res[(i-2)%2] + nums[i])
return max(res[0], res[1])
221 Maximum Square
类型:二维DP
Time Complexity O(N^2)
Space Complexity O(N^2)
class Solution(object):
def maximalSquare(self, matrix):
if not matrix: return 0
m , n = len(matrix), len(matrix[0])
dp = [[ 0 if matrix[i][j] == '0' else 1 for j in range(0, n)] for i in range(0, m)]
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
else:
dp[i][j] = 0
res = max(max(row) for row in dp)
return res ** 2
300 Longest Increacing Sequence
类型:一维DP
Time Complexity O(N^2)
Space Complexity O(N)
class Solution:
def lengthOfLIS(self, nums):
if not nums: return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
from leetcode.
Related Issues (20)
- Day 7 | 3/20/20 HOT 1
- 76. Minimum Window Substring
- 215 -> 研究下Quick Select算法
- Day 3. 02/10/20 HOT 3
- 973. K Closest Points to Origin
- 67. Add Binary HOT 2
- 491. Increasing Subsequences
- 1027
- Day 4. 02/11/20 HOT 5
- 350 Intersection of Two Arrays II
- 297. Serialize and Deserialize Binary Tree
- Day 5. 02/12/20
- Day 5. 02/15/20 HOT 3
- [Weekly Plan] Day 7 - 12. (New Start) | 2/18 - 2/22 HOT 6
- Day 5 | 2/20/20 HOT 6
- 560. Subarray Sum Equals K HOT 1
- Sliding Windows HOT 2
- Day 6 HOT 2
- Week 3
- 116. Populating Next Right Pointers in Each Node
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from leetcode.