动态规划、贪心
https://leetcode.com/problems/climbing-stairs/description/
https://leetcode.com/problems/triangle/description/
https://leetcode.com/problems/maximum-product-subarray/description/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/#/description
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
https://leetcode.com/problems/longest-increasing-subsequence
https://leetcode.com/problems/coin-change/
https://leetcode.com/problems/edit-distance/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
https://leetcode.com/problems/lemonade-change/description/
https://leetcode.com/problems/assign-cookies/description/
https://leetcode.com/problems/walking-robot-simulation/description/
70.爬楼梯
class Solution:
def climbStairs(self, n: int) -> int:
# 1 <= n <= 45
# 状态定义，数组长度+1，兼容n=1的情况
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
# 从2开始（因为要-2）到数组结束
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:
f1 = f2 = 1
for i in range(2, n + 1):
# f = f1 + f2
# f1 = f2
# f2 = f
f1, f2 = f2, f1 + f2
return f2
120.三角形最小路径和
from typing import List
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# 自底向上递推，dp[i,j]=dp[i,j]+min(dp[i+1,j],dp[i+1,j+1])
# 状态压缩，dp数组只要一维就可以了
# 初始化dp为triangle[-1]
dp = triangle[-1]
for i in range(len(triangle) - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
return dp[0]
152.乘积最大子数组
from typing import List
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0] * 2 for _ in range(n)]
res = dp[0][0] = dp[0][1] = nums[0]
for i in range(1, n):
if nums[i] >= 0:
dp[i][1] = max(dp[i - 1][1] * nums[i], nums[i])
dp[i][0] = min(dp[i - 1][0] * nums[i], nums[i])
else:
dp[i][1] = max(dp[i - 1][0] * nums[i], nums[i])
dp[i][0] = min(dp[i - 1][1] * nums[i], nums[i])
res = max(dp[i][1], res)
return res
状态压缩
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
res = curMax = curMin = nums[0]
for i in range(1, n):
curMax, curMin = curMax * nums[i], curMin * nums[i]
curMax, curMin = max(curMax, curMin, nums[i]), min(curMax, curMin, nums[i])
res = max(res, curMax)
return res
300.最长递增子序列
方式一（DP）：
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1 for _ in range(n)]
res = 1
for i in range(1, n):
for j in range(0, i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
res = max(res, dp[i])
return res
方式二（二分）：
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
res = [nums[0]]
for i in range(1, len(nums)):
# 大于最大的，就追加
if nums[i] > res[-1]:
res.append(nums[i])
else: # 否则替换大于等于nums[i]的最小的那个
index = bisect_left(res, nums[i])
res[index] = nums[i]
return len(res)
322.零钱兑换
```
### 72.编辑距离
[链接](https://leetcode.cn/problems/edit-distance/)
```python