各大网站开发语言,木模板价格,wordpress 3.5.1 漏洞,wordpress 删除边栏121. 买卖股票的最佳时机
贪婪思想#xff1a;力争在最低成本买入#xff0c;最高利润卖出。 [7,1,5,3,6,4] 可以先假设在第一天买入和卖出#xff0c;这时最低成本是7#xff0c;最大利润是7-70 然后假设在第二天买入和卖出#xff0c;成本就是1#xff0c;利润也是0 第…121. 买卖股票的最佳时机
贪婪思想力争在最低成本买入最高利润卖出。 [7,1,5,3,6,4] 可以先假设在第一天买入和卖出这时最低成本是7最大利润是7-70 然后假设在第二天买入和卖出成本就是1利润也是0 第三天因为成本比第二天高所以不买入只卖出利润就是5-14 以此类推 每次遍历都检测最小成本和最大利润
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 profit300. 最长递增子序列
要找到一个数组中最长严格递增子序列Longest Increasing Subsequence简称LIS的长度动态规划是一种有效的方法。这个问题的关键在于找出一个状态定义使得状态之间的转移是可解的。 动态规划解法 状态定义定义dp[i]为考虑前i个元素以第i个数字结尾的最长递增子序列的长度。注意这里的子序列至少包含一个数即第i个数本身。 状态转移方程要计算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]。 初始化因为最长递增子序列至少包含自己所以每个元素的LIS长度初始值至少为1即dp[i] 1。 计算顺序从左到右依次计算每个dp[i]因为计算dp[i]时需要用到前面的dp[j]。 结果最长递增子序列的长度为所有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 找出状态转移方程 如果text1[i-1] text2[j-1]即当前两个字符相等那么dp[i][j] dp[i-1][j-1] 1。因为我们找到了一个公共元素可以在以前的LCS长度上加1。如果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]*(m1) for _ in range(n1)]for i in range(1, n1): # 先从第一个维度遍历for j in range(1, m1): #从第二个维度遍历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. 编辑距离
解题思路动态规划不用管具体改了什么字符只管当前状态由什么决定。一般都是跟左边、上边、左上有关。 解释这三个操作对应的状态转移方程我们先要理解每个操作的含义和如何影响字符串的转换 插入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个字符的最优方法并在此基础上进行一次插入操作。 删除dp[i][j] dp[i-1][j] 1 这表示为了将word1的前i个字符转换为word2的前j个字符我们考虑了从word1的前i个字符中删除最后一个字符使其与word2的前j个字符更接近。因为我们进行了删除操作所以操作次数加1。删除操作是基于假设我们已经找到了将word1的前i-1个字符转换为word2的前j个字符的最优方法并在此基础上进行一次删除操作。 替换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]*(n1) for _ in range(m1)]# 初始化左上角dp[0][0] 0# 初始化第一行for i in range(1, m1):dp[i][0] i# 初始化第一列for j in range(1, n1):dp[0][j] jfor i in range(1, m1):for j in range(1, n1):# 如果字符相等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) 移动过来的。基于这个原理我们可以构建一个动态规划方程来求解问题。 动态规划方法 状态定义定义 dp[i][j] 为从起点 (0, 0) 到达点 (i, j) 的路径总数。 状态转移方程因为到达点 (i, j) 只能从 (i-1, j) 或 (i, j-1) 两个点移动一步到达所以 dp[i][j] dp[i-1][j] dp[i][j-1]。 初始化初始化第一行和第一列的值为1因为从起点到达第一行和第一列的任意位置只有一种路径要么一直向右要么一直向下。 填表按顺序计算 dp 数组的其余部分。 结果dp[m-1][n-1] 即为从起点到达终点的路径总数。 解释 初始化时dp 的每个元素都被设置为1因为到达第一行或第一列的任意位置的路径只有一条。通过双层循环我们更新 dp 数组的值使其反映到达每个位置的路径数。最后dp[m-1][n-1] 存储了到达右下角的路径总数。 这种动态规划方法利用了问题的子结构问题的解可以通过其子问题的解来构建和重叠子问题相同的子问题被多次计算特点使得我们可以高效地求解原问题。 152. 乘积最大子数组 要解决这个问题我们可以同时跟踪到当前位置为止的最大乘积和最小乘积因为一个很小的负数乘以一个负数可能变成一个很大的正数。这意味着我们需要维护两个动态规划数组一个用于追踪最大乘积另一个用于追踪最小乘积。 修改后的算法 定义状态 max_dp[i] 表示到第i个元素为止的最大连续子数组乘积。min_dp[i] 表示到第i个元素为止的最小连续子数组乘积考虑负负得正的情况。 状态转移方程 对于每个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]) 初始化 max_dp[0] min_dp[0] nums[0]因为第一个元素前面没有其他元素所以它自己就是一个子数组。 遍历数组 按照状态转移方程更新max_dp和min_dp。 找到最大乘积 最大乘积不一定是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. 打家劫舍 问题的关键是找到一个状态定义以及如何根据前面的状态来更新当前的状态。问题可以描述为给定一个整数数组从中选取出一些元素这些元素的总和最大但不能选取相邻的元素。 动态规划思路 状态定义定义dp[i]为到达第i个房屋时能够偷窃到的最高金额。 状态转移方程对于第i个房屋有两种选择 不偷这个房屋那么总金额就是到前一个房屋为止的最高金额即dp[i-1]偷这个房屋那么总金额就是这个房屋的金额加上到前前个房屋为止的最高金额即nums[i] dp[i-2]因为不能偷相邻的房屋。 所以dp[i] max(dp[i-1], nums[i] dp[i-2])。 初始化 dp[0] nums[0]只有一个房屋时只能偷这一个如果有两个房屋应该选择金额较大的那个所以dp[1] max(nums[0], nums[1])。 计算顺序从左到右依次计算每个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]
