湖北建设信息网站 联系方式/设计网络推广方案

121. 买卖股票的最佳时机

贪婪思想：力争在最低成本买入，最高利润卖出。
[7,1,5,3,6,4]
可以先假设在第一天买入和卖出，这时最低成本是7，最大利润是7-7=0
然后假设在第二天买入和卖出，成本就是1，利润也是0
第三天因为成本比第二天高，所以不买入，只卖出，利润就是5-1=4
以此类推
每次遍历都检测最小成本和最大利润

class Solution:def maxProfit(self, prices: List[int]) -> int:# 贪婪思想，初始化成本和利润cost, profit = float('inf'), 0# 成本是取最小的，利润是选最大的# 遍历过程中不断更新最小成本和最大利润for price in prices:cost = min(cost, price)profit = max(profit, price-cost)return profit

122. 买卖股票的最佳时机 II

单独的交易：看今天卖和昨天买的差值
连续上涨：等差数列

class Solution:def maxProfit(self, prices: List[int]) -> int:# 初始化利润profit = 0# 如果当前比前一天的价格更高，那就是要昨天买今天买# 对于等差数列，在同一天卖跟每天都卖是一样的for i in range(1, len(prices)):# 把所有天的利润加起来，如果是负利润，那么就是0（不卖）temp = max(prices[i]-prices[i-1], 0)profit += tempreturn profit

300. 最长递增子序列

要找到一个数组中最长严格递增子序列（Longest Increasing Subsequence，简称LIS）的长度，动态规划是一种有效的方法。这个问题的关键在于找出一个状态定义，使得状态之间的转移是可解的。

动态规划解法：

1. 状态定义：定义dp[i]为考虑前i个元素，以第i个数字结尾的最长递增子序列的长度。注意，这里的子序列至少包含一个数，即第i个数本身。

2. 状态转移方程：要计算dp[i]，需要考虑比第i个数小的所有数。对于任意一个小于i的下标j，如果nums[j] < nums[i]，那么nums[i]可以接在nums[j]后面形成一个更长的递增子序列。因此，dp[i] = max(dp[i], dp[j] + 1)对所有的0 <= j < i且nums[j] < nums[i]。

3. 初始化：因为最长递增子序列至少包含自己，所以每个元素的LIS长度初始值至少为1，即dp[i] = 1。

4. 计算顺序：从左到右依次计算每个dp[i]，因为计算dp[i]时需要用到前面的dp[j]。

5. 结果：最长递增子序列的长度为所有dp[i]中的最大值。

代码实现

def lengthOfLIS(nums):if not nums:return 0n = len(nums)dp = [1] * n  # 初始化dp数组，每个元素的LIS长度初始值为1for i in range(1, n):for j in range(i):if nums[j] < nums[i]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)  # LIS长度为dp数组中的最大值

1143. 最长公共子序列

解题思路：动态规划
需要构建辅助矩阵，多加一行和一列
当前的状态由左上、左边和上边决定。如果相等，那么当前状态是由左对角线（左上角）的加自己1决定的；如果不相等，那么当前状态需要在左边和上边中选择一个最大的扩展其状态。

步骤 1：

理解问题和目标 我们的目标是找出两个字符串text1和text2的最长公共子序列的长度。一个子序列是指从原字符串中删除一些（或不删除）字符而不改变其余字符的顺序得到的新字符串。

步骤 2：

定义 DP 数组 定义二维数组dp，其中dp[i][j]表示text1中前i个字符和text2中前j个字符的最长公共子序列的长度。注意，dp[i][j]是基于text1[0..i-1]和text2[0..j-1]的子序列。

步骤 3：

找出状态转移方程

1. 如果text1[i-1] == text2[j-1]，即当前两个字符相等，那么dp[i][j] = dp[i-1][j-1] + 1。因为我们找到了一个公共元素，可以在以前的LCS长度上加1。
2. 如果text1[i-1] != text2[j-1]，即当前两个字符不相等，那么dp[i][j] = max(dp[i-1][j], dp[i][j-1])。此时，LCS的长度是两种情况中的较大值。

步骤 4：

初始化 DP 数组 初始化dp数组的第一行和第一列为0，因为任何字符串与空字符串的最长公共子序列长度都是0。

步骤 5：

填充 DP 数组 从dp[1][1]开始，根据状态转移方程逐步填充整个dp数组。

步骤 6：

解读结果 dp数组的最后一个元素dp[len(text1)][len(text2)]即为text1和text2的最长公共子序列的长度。

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:# 辅助矩阵m, n = len(text1), len(text2)# 都加1个维度，方便后续操作不超索引dp = [[0]*(m+1) for _ in range(n+1)]for i in range(1, n+1): # 先从第一个维度遍历for j in range(1, m+1): #从第二个维度遍历if text1[j-1] == text2[i-1]: # 因为是从1开始，所以要看前面的一位dp[i][j] = dp[i-1][j-1]+1 # 相等，那么就是加上前面的最长子序列和当前的元素else:dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 不相等，就将左边对角线附近的最长子序列数扩展到当前return dp[n][m]

64. 最小路径和

动态规划
建立一个辅助矩阵，第一行和第一列的路径和只能是从左边或者右边来，所以辅助矩阵维度保持不变，初始化为0，将第一行第一列的值按照路径和定义加进来。
状态转移公式就是dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:m = len(grid)n = len(grid[0])dp = [[0] * (n) for _ in range(m)]# 初始化起点dp[0][0] = grid[0][0]# 初始化第一列，每个位置只能从上方来for i in range(1, m):dp[i][0] = dp[i-1][0] + grid[i][0]# 初始化第一行，每个位置只能从左边来for j in range(1, n):dp[0][j] = dp[0][j-1] + grid[0][j]# 动态规划for i in range(1, m):for j in range(1, n):# 选择左边和上面的最小值加上当前值dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]return(dp[-1][-1])  # 输出最后一个位置的值，即右下角的最小路径和

72. 编辑距离

解题思路：动态规划，不用管具体改了什么字符，只管当前状态由什么决定。一般都是跟左边、上边、左上有关。

解释这三个操作对应的状态转移方程，我们先要理解每个操作的含义和如何影响字符串的转换：

1. 插入：dp[i][j] = dp[i][j-1] + 1

   • 这意味着为了从word1的前i个字符转换到word2的前j个字符，我们考虑了在word1的前i个字符基础上，通过在末尾插入一个与word2[j-1]相同的字符，使其与word2的前j个字符匹配。因为我们插入了一个字符，所以操作次数加1。
   • 插入操作是基于假设我们已经找到了将word1的前i个字符转换为word2的前j-1个字符的最优方法，并在此基础上进行一次插入操作。

2. 删除：dp[i][j] = dp[i-1][j] + 1

   • 这表示为了将word1的前i个字符转换为word2的前j个字符，我们考虑了从word1的前i个字符中删除最后一个字符，使其与word2的前j个字符更接近。因为我们进行了删除操作，所以操作次数加1。
   • 删除操作是基于假设我们已经找到了将word1的前i-1个字符转换为word2的前j个字符的最优方法，并在此基础上进行一次删除操作。

3. 替换：dp[i][j] = dp[i-1][j-1] + 1

   • 这意味着为了从word1的前i个字符转换到word2的前j个字符，我们考虑了将word1的第i个字符替换为word2的第j个字符（这两个字符不同），使之匹配。因为我们替换了一个字符，所以操作次数加1。
   • 替换操作是基于假设我们已经找到了将word1的前i-1个字符转换为word2的前j-1个字符的最优方法，并在此基础上进行一次替换操作。

这些状态转移方程的核心思想是，通过局部最优解（即最少的操作次数）来逐步构建全局最优解。在每个位置dp[i][j]，我们都尝试三种操作，并从中选择一种使得总操作数最小的方案，以此保证最终得到的是将整个word1转换为word2所需的最少操作次数。

class Solution:def minDistance(self, word1: str, word2: str) -> int:m,n = len(word1), len(word2)# 动态规划dp = [[0]*(n+1) for _ in range(m+1)]# 初始化左上角dp[0][0] = 0# 初始化第一行for i in range(1, m+1):dp[i][0] = i# 初始化第一列for j in range(1, n+1):dp[0][j] = jfor i in range(1, m+1):for j in range(1, n+1):# 如果字符相等if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1] # 那就不操作，继承以前的操作else:dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1 # 否则，就操作，加上当前字符return(dp[m][n])

62. 不同路径

解题思路：又是动态规划。
要确定的点是当前状态是个啥，比如上题就是操作数，这题就是路径数；
然后确定当前状态被什么决定，比如上题是根据左上、左边、上边，本题就是根据左边和上边，理解题意后写出状态转移公式，代码化。

class Solution:def uniquePaths(self, m: int, n: int) -> int:# 辅助矩阵dp = [[1]*n for _ in range(m)]# 状态转移公式for i in range(1, m):for j in range(1, n):# 当前状态是指从原点到当前点的路径总和，由从上和左边来的路径决定dp[i][j] = dp[i-1][j] + dp[i][j-1]return(dp[-1][-1])

考虑到机器人每次只能向下或者向右移动，我们可以发现到达网格中任意位置 (i, j) 的路径数是到达其上方位置 (i-1, j)
和左侧位置 (i, j-1) 的路径数之和。这是因为，从起点到达 (i, j) 的每条路径，都是通过最后一步从 (i-1, j)
或 (i, j-1) 移动过来的。基于这个原理，我们可以构建一个动态规划方程来求解问题。

动态规划方法

1. 状态定义：定义 dp[i][j] 为从起点 (0, 0) 到达点 (i, j) 的路径总数。

2. 状态转移方程：因为到达点 (i, j) 只能从 (i-1, j) 或 (i, j-1) 两个点移动一步到达，所以 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

3. 初始化：初始化第一行和第一列的值为1，因为从起点到达第一行和第一列的任意位置只有一种路径（要么一直向右，要么一直向下）。

4. 填表：按顺序计算 dp 数组的其余部分。

5. 结果：dp[m-1][n-1] 即为从起点到达终点的路径总数。

解释

• 初始化时，dp 的每个元素都被设置为1，因为到达第一行或第一列的任意位置的路径只有一条。
• 通过双层循环，我们更新 dp 数组的值，使其反映到达每个位置的路径数。
• 最后，dp[m-1][n-1] 存储了到达右下角的路径总数。

这种动态规划方法利用了问题的子结构（问题的解可以通过其子问题的解来构建）和重叠子问题（相同的子问题被多次计算）特点，使得我们可以高效地求解原问题。

152. 乘积最大子数组

要解决这个问题，我们可以同时跟踪到当前位置为止的最大乘积和最小乘积（因为一个很小的负数乘以一个负数可能变成一个很大的正数）。这意味着我们需要维护两个动态规划数组，一个用于追踪最大乘积，另一个用于追踪最小乘积。

修改后的算法：

1. 定义状态：

   • max_dp[i] 表示到第i个元素为止的最大连续子数组乘积。
   • min_dp[i] 表示到第i个元素为止的最小连续子数组乘积（考虑负负得正的情况）。

2. 状态转移方程：

   • 对于每个i，有三种情况需要考虑（nums[i]本身、nums[i] * max_dp[i-1]和nums[i] * min_dp[i-1]），因为当前元素可以独自成为最大乘积子数组，或者可以与前一个子数组的最大/最小乘积相乘形成新的最大/最小乘积。
   • max_dp[i] = max(nums[i], nums[i] * max_dp[i-1], nums[i] * min_dp[i-1])
   • min_dp[i] = min(nums[i], nums[i] * max_dp[i-1], nums[i] * min_dp[i-1])

3. 初始化：

   • max_dp[0] = min_dp[0] = nums[0]，因为第一个元素前面没有其他元素，所以它自己就是一个子数组。

4. 遍历数组：

   • 按照状态转移方程更新max_dp和min_dp。

5. 找到最大乘积：

   • 最大乘积不一定是max_dp[-1]，因为最大乘积可能出现在数组的任何位置，所以需要遍历max_dp数组找到最大值。

class Solution:def maxProduct(self, nums: List[int]) -> int:# 因为负负得正，所以不能只看大于0的，维护两个辅助数组max_dp = [1] * len(nums)min_dp = [1] * len(nums)max_dp[0] = nums[0]min_dp[0] = nums[0]# 最大乘积的数组状态由当前元素；如果前面是正的，乘当前；最小乘积有可能是负的，当前也可能是负的for i in range(1, len(nums)):max_dp[i] = max(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i])min_dp[i] = min(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i])return max(max_dp)

198. 打家劫舍

问题的关键是找到一个状态定义，以及如何根据前面的状态来更新当前的状态。问题可以描述为：给定一个整数数组，从中选取出一些元素，这些元素的总和最大，但不能选取相邻的元素。

动态规划思路

1. 状态定义：定义dp[i]为到达第i个房屋时能够偷窃到的最高金额。

2. 状态转移方程：对于第i个房屋，有两种选择：

   • 不偷这个房屋，那么总金额就是到前一个房屋为止的最高金额，即dp[i-1]；
   • 偷这个房屋，那么总金额就是这个房屋的金额加上到前前个房屋为止的最高金额，即nums[i] + dp[i-2]（因为不能偷相邻的房屋）。
     所以，dp[i] = max(dp[i-1], nums[i] + dp[i-2])。

3. 初始化：

   • dp[0] = nums[0]，只有一个房屋时，只能偷这一个；
   • 如果有两个房屋，应该选择金额较大的那个，所以dp[1] = max(nums[0], nums[1])。

4. 计算顺序：从左到右依次计算每个dp[i]。

class Solution:def rob(self, nums: List[int]) -> int:# 处理只有一个元素的情况if len(nums) == 1:return nums[0]# 直接复制数组作为辅助数组dp = nums.copy()# 第二个状态取前两个的最大值dp[1] = max(nums[0], nums[1])# dp的当前状态是到当前的最高金额（和）for i in range(2, len(nums)):# 要么不偷，要么偷dp[i] = max(dp[i-1], dp[i-2] + nums[i])return dp[-1]