DP 主要步骤：
- dp 含义，1D， 2D
- 目标
- 递推公式, 状态转移方程
- 初始化
- 遍历顺序
-
举例
509. 斐波那契数
- 思路
- example
- DP, 迭代, 自下而上， dp table
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
dp = [0 for _ in range(n+1)]
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
- 空间优化
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
first, second = 0, 1
for i in range(2, n+1):
third = second + first
first = second
second = third
return third
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
first, second = 0, 1
for i in range(2, n+1):
third = first + second
first = second
second = third
return third
- DP, 递归，自上而下 (暴力解）
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return self.fib(n-1) + self.fib(n-2)
-
DP, 递归，自上而下, 备忘录（记亿化）
class Solution:
def fib(self, n: int) -> int:
def helper(n):
if dp[n] != -1:
return dp[n]
if n == 0:
return 0
if n == 1:
return 1
dp[n] = helper(n-1) + helper(n-2)
return dp[n]
dp = [-1] * (n+1)
return helper(n)
70. 爬楼梯
- 思路
- example
- DP
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return n
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
- 空间优化
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
first, second = 1, 1
for i in range(2, n+1):
third = first + second
first = second
second = third
return third
746. 使用最小花费爬楼梯
- 思路
- example
- 最低花费
- 顶层：下标n
初始化
dp[0] = 0 不需要花费
dp[1] = 0 不需要花费
for i > 1:
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
目标：dp[n]
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0 for _ in range(n+1)]
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
return dp[n]
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0 for _ in range(n+1)]
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
return dp[n]
- 可空间优化成
