动态规划
- 确定基础情况 base case
- 最优子结构
- 状态转移方程
70. 爬楼梯
70. 爬楼梯
class Solution(object):
def climbStairs(self, n):
f1 = 1
f2 = 2
if n == 1:
return f1
if n == 2:
return f2
for _ in range(3, n + 1):
fn = f2 + f1
f1 = f2
f2 = fn
return fn
def climbStairs(self, n):
dp = [0] * (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]
121. 买卖股票的最佳时机
121. 买卖股票的最佳时机
class Solution:
# 暴力循环 两次遍历
def maxProfit(self, prices) -> int:
res = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
res = max(res, prices[j] - prices[i])
return res
# 一次遍历，记录最低点
def maxProfit2(self, prices) -> int:
res = 0
low = float("inf")
for i in range(len(prices)):
low = min(low, prices[i]) # 取最左最小价格
res = max(res, prices[i] - low) # 直接取最大区间利润
return res
198. 打家劫舍
198. 打家劫舍
# 当前偷不偷，取决于前一个房屋和前两个房屋是否被偷了
class Solution:
def rob(self, nums) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[-1]
def rob2(self, nums):
return self.dp(self, nums, 0)
def dp(self, nums, start):
if start >= len(nums):
return 0
# self.dp(nums, start + 1) 不抢，去下一家
# self.dp(nums, start + 2) + nums[start] 抢，去下下家
res = max(self.dp(nums, start + 1), self.dp(nums, start + 2) + nums[start])
return res
213. 打家劫舍 II
213. 打家劫舍 II
# 这个和基础的打家劫舍的区别在于，首尾相连了
# 情形一：不包含首尾元素
# 情形二：包含首，不包含尾
# 情形三：不包含首，包含尾
class Solution:
def rob(self, nums) -> int:
if len(nums) == 1:
return nums[0]
first = self.rob_range(nums[1:]) # 不抢第一家
last = self.rob_range(nums[:-1]) # 不抢最后一家
return max(first, last)
def rob_range(self, nums):
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
if i == 1:
dp[i] = max(dp[i - 1], nums[i])
else:
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[-1]
322. 零钱兑换
322. 零钱兑换
class Solution:
def coinChange(self, coins, amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return -1 if dp[amount] == amount + 1 else dp[amount]
337. 打家劫舍 III
337. 打家劫舍 III
# 如果抢了当前节点，那么孩子结点就不能抢
# 如果没有抢当前节点，可以抢左右孩子节点
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rob(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return root.val
# 抢父节点
val_1 = root.val
if root.left:
val_1 += self.rob(root.left.left) + self.rob(root.left.right)
if root.right:
val_1 += self.rob(root.right.left) + self.rob(root.right.right)
# 不抢父节点
val_2 = self.rob(root.left) + self.rob(root.right)
return max(val_1, val_2)
def rob2(self, root: TreeNode):
dp = self.traversal(root)
return max(dp)
def traversal(self, root: TreeNode):
# 空节点，不偷
if not root:
return (0, 0)
left = self.traversal(root.left)
right = self.traversal(root.right)
# 不偷当前节点, 偷子节点
val_1 = max(left[0], left[1]) + max(right[0], right[1])
# 偷当前节点, 不偷子节点
val_2 = root.val + left[0] + right[0]
return (val_1, val_2)
509. 斐波那契数
509. 斐波那契数
class Solution:
def fib(self, n: int) -> int:
if n == 1 or n == 2:
return 1
return self.fib(n - 1) + self.fib(n - 2)
def fib2(self, n):
arr = [0] * (n + 1)
return self.hepler(arr, n)
def hepler(self, arr, n):
if n == 0 or n == 1:
return n
if arr[n] != 0:
return arr[n]
arr[n] = self.hepler(arr, n - 1) + self.hepler(arr, n - 2)
return arr[n]
def fib3(self, n: int) -> int:
if n == 0:
return 0
dp = [0] * (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]
746. 使用最小花费爬楼梯
746. 使用最小花费爬楼梯
class Solution:
def minCostClimbingStairs(self, cost):
dp = [0] * len(cost)
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, len(cost)):
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
return min(dp[len(cost) - 1], dp[len(cost) - 2])
146. LRU 缓存
146. LRU 缓存
class ListNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.hashmap = {}
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def remove_node(self, node: ListNode):
node.prev.next = node.next
node.next.prev = node.prev
def add_to_head(self, node: ListNode):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def move_to_head(self, node: ListNode):
self.remove_node(node)
self.add_to_head(node)
def remove_tail(self):
node = self.tail.prev
self.remove_node(node)
return node
def get(self, key: int) -> int:
if key not in self.hashmap:
return -1
node = self.hashmap[key]
self.move_to_head(node=node)
return node.val
def put(self, key: int, value: int) -> None:
if key not in self.hashmap:
node = ListNode(key, value)
self.hashmap[key] = node
self.add_to_head(node)
self.size += 1
if self.size > self.capacity:
removed = self.remove_tail()
self.hashmap.pop(removed.key)
self.size -= 1
else:
node = self.hashmap[key]
node.val = value
self.move_to_head(node)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)