动态规划算法练习

本文最后更新于：2023年12月5日下午

记录动态规划刷题方案。

2008. 出租车的最大盈利

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

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

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

给你 n 和 rides ，请你返回在最优接单方案下，你能盈利最多多少元。

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

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 。

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

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 。

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

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] 的子序列。

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 ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

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. 最长公共子序列

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

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

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

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

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 位带符号整数。

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]