本文最后更新于:2024年1月14日 晚上

记录动态规划刷题方案。

2008. 出租车的最大盈利

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1n ,你想要从 1 开到 n ,通过接乘客订单盈利。你只能沿着编号递增的方向前进,不能改变方向。

乘客信息用一个下标从 0 开始的二维数组 rides 表示,其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ,愿意支付 tipi 元的小费。

每一位 你选择接单的乘客 i ,你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。

给你 nrides ,请你返回在最优接单方案下,你能盈利 最多 多少元。

**注意:**你可以在一个地点放下一位乘客,并在同一个地点接上另一位乘客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import bisect
class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
rides.sort(key=lambda x:x[1])
earn_res = list()

for ride in rides:
start, end, tip = ride
insert_index = bisect.bisect_right(earn_res, start, key=lambda x:x[0])
max_value = end - start + tip
if insert_index > 0:
max_value += earn_res[insert_index - 1][1]
if not earn_res:
earn_res.append([end, max_value])
elif earn_res[-1][0] == end:
earn_res[-1][1] = max(earn_res[-1][1], max_value)
else:
if earn_res[-1][1] < max_value:
earn_res.append([end, max_value])

return earn_res[-1][1]

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s

**注意:**不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
left_str_queue = [s]
visited_length = set()
while left_str_queue:
temp_q = []
for left_str in left_str_queue:
for word in wordDict:
length = len(word)
if len(left_str) < length:
continue
if left_str[:length] == word:
left = left_str[length:]
if len(left) == 0:
return True
if len(left) not in visited_length:
temp_q.append(left)
visited_length.add(len(left))
left_str_queue = temp_q
return False

322. 零钱兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
res_dict = dict()
res_dict[amount] = 0
q = [amount]
visited_node = set()
while q:
temp_q = []
for data in q:
for coin in coins:
if coin <= data:
left = data - coin
if left not in res_dict:
res_dict[left] = float('inf')
res_dict[left] = min(res_dict[left], res_dict[data] + 1)
if left > 0:
if left not in visited_node:
temp_q.append(left)
visited_node.add(left)
q = temp_q
if 0 not in res_dict:
return -1
else:
return res_dict[0]

300. 最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1
2
3
4
5
6
7
8
9
10
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp = [1] * len(nums)
for index in range(len(nums)):
for j in range(index):
if nums[j] < nums[index]:
dp[index] = max(dp[index], dp[j] + 1)
return max(dp)

120. 三角形最小路径和

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 ii + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
q = triangle[0]

level_num = len(triangle)
for leven_index in range(1, level_num):
cur_level_data = triangle[leven_index]
temp_q = [1e6] * len(cur_level_data)
for index, value in enumerate(q):
temp_q[index] = min(value + cur_level_data[index], temp_q[index])
temp_q[index + 1] = min(value + cur_level_data[index + 1], temp_q[index + 1])
q = temp_q
return min(q)

1143. 最长公共子序列

给定两个字符串 text1text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace""abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
last_line = [0] * (len(text1) + 1)
for index_2, char_2 in enumerate(text2):
last_value = 0
cur_line = [0] * (len(text1) + 1)
for index_1, char_1 in enumerate(text1):
if char_1 == char_2:
cur_line[index_1 + 1] = last_line[index_1] + 1
else:
cur_line[index_1 + 1] = max(last_line[index_1 + 1], last_value)
last_value = cur_line[index_1 + 1]
last_line = cur_line
# print(cur_line)
return last_value

518. 零钱兑换 II ********

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0]*(amount+1) # 初始化
dp[0] = 1 # 合法的初始化:凑出金额0的组合只有一种,即不选任何硬币

# 完全背包:优化后的状态转移
for coin in coins: # 第一层循环:遍历硬币
for j in range(coin, amount+1): # 第二层循环:遍历背包【正序】
dp[j] += dp[j-coin]

return dp[amount]




文章链接:
https://www.zywvvd.com/notes/study/algorithm/dp/dp/


“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

动态规划算法练习
https://www.zywvvd.com/notes/study/algorithm/dp/dp/
作者
Yiwei Zhang
发布于
2022年5月19日
许可协议