做网站让用seo刷新是哪个键,山西省太原建设工程信息网站,顺德网站建设制作,wordpress 分类文章排序动态规划解题步骤-5部曲
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
70. 爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到…动态规划解题步骤-5部曲
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
70. 爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶
解题思路
f(n) f(n-2) f(n-1)
Python代码
class Solution:def climbStairs(self, n: int) - int:n_1 n_2 1if n 1:return 1for i in range(2, n1):f_n n_1 n_2n_2 n_1n_1 f_nreturn f_n118. 杨辉三角
题目描述
给定一个非负整数 numRows生成杨辉三角的前 numRows 行。
解题思路
杨辉三角的每个元素是上一行左右两个元素之和边界元素为 1。用一个二维列表来存储结果每行第一个和最后一个元素固定为 1其他元素是它左上和右上的和。
Python代码
class Solution:def generate(self, numRows: int) - List[List[int]]:if numRows 0:return []res [[1]]if numRows 1:return resres.append([1, 1])if numRows 2:return resfor i in range(3, numRows1):last_nums res[-1] cur_nums [1]numRows len(last_nums)for j in range(numRows-1):cur_nums.append(last_nums[j]last_nums[j1])cur_nums.append(1)res.append(cur_nums)return res198. 打家劫舍
题目描述
你是一个专业的窃贼计划偷窃沿街的房屋。每间房内都藏有一定的现金如果相邻的两间房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动报警装置的情况下今晚能够偷窃到的最高金额。
解题思路
使用动态规划来解决。假设 dp[i] 表示前 i 间房屋所能偷窃的最高金额则状态转移方程为 dp[i] max(dp[i-1], dp[i-2] nums[i])初始条件为 dp[0] nums[0] 和 dp[1] max(nums[0], nums[1])。
Python代码
class Solution:def rob(self, nums: List[int]) - int:n len(nums)dp [0]*nif n 1:return nums[0]dp[0] nums[0]dp[1] max(nums[0], nums[1])for i in range(2, n):dp[i] max(dp[i-1], nums[i]dp[i-2])return dp[n-1]279. 完全平方数
题目描述
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
解题思路
使用动态规划来解决。假设 dp[i] 表示组成整数 i 所需要的最少的完全平方数的数量则状态转移方程为 dp[i] min(dp[i - 1* 1] 1dp[i - 2 * 2] 1... , dp[i - j * j] 1)其中 j * j 是当前平方数由此来更新每一个 dp 位置。 求和问题
Python代码
class Solution:def numSquares(self, n: int) - int:dp [0] * (n 1)dp[1] 1for i in range(2, n 1):j 1res float(inf)while j * j i:res min(res, dp[i - j * j] 1)j 1dp[i] resreturn dp[n]322. 零钱兑换
题目描述
给定不同面额的硬币和一个总金额。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。
解题思路
完全背包问题 背包容量总金额 物品重量硬币价值 物品价值数量
假设 dp[i] 表示金额 i 所需的最小硬币数则状态转移方程为 dp[i] min(dp[i], dp[i - coin] 1)其中 coin 是可选的硬币面值。
完全背包的物品可以被取无数次因此完全背包的内循环为正序当前物品可以被重复取用
Python代码
class Solution:def coinChange(self, coins: List[int], amount: int) - int:n len(coins)dp [float(inf)] * (amount 1)dp[0] 0for i in range(1, amount 1):if i % coins[0] 0:dp[i] i // coins[0]for i in range(1, n):for j in range(coins[i], amount 1):dp[j] min(dp[j], dp[j-coins[i]] 1)return -1 if dp[amount] float(inf) else dp[amount]139. 单词拆分
题目描述
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 输入: s “applepenapple”, wordDict [“apple”, “pen”] 输出: true
解题思路
可以转化成完全背包问题而且是排列问题字符串s是背包字符串列表里的字符是物品 dp[i] 表示前 i 个字符是否能被拆分; 因为是排列问题所以外循环遍历背包内循环遍历物品
Python代码
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:n len(s)word_n len(wordDict)dp [False] * (n 1)dp[0] Truefor j in range(1, n1):for i in range(word_n):if j len(wordDict[i]):dp[j] (dp[j] or (s[j - len(wordDict[i]):j] wordDict[i] and dp[j-len(wordDict[i])]))# print(dp)return dp[n]300. 最长递增子序列
题目描述
给定一个无序的整数数组找到其中最长递增子序列的长度。
解题思路
使用动态规划来解决。假设 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度则状态转移方程为dp[i] max(dp[j] 1)其中 j 从 0 到 i-1 且 nums[j] nums[i]。
Python代码
class Solution:def lengthOfLIS(self, nums: List[int]) - int:n len(nums)dp [1] * nres 1for i in range(1, n):for j in range(i):if nums[j] nums[i]:dp[i] max(dp[i], dp[j] 1)res max(res, dp[i])return res152. 乘积最大子数组
题目描述
给你一个整数数组 nums 请你找出数组中乘积最大的连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。 输入: nums [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
解题思路
使用动态规划来解决。维护两个变量 max_val 和 min_val表示以当前元素为结尾的子数组的最大乘积和最小乘积然后遍历数组更新这两个值。
Python代码
class Solution:def maxProduct(self, nums: List[int]) - int:if not nums:return 0max_val min_val res nums[0]for i in range(1, len(nums)):if nums[i] 0:max_val, min_val min_val, max_valmax_val max(nums[i], max_val * nums[i])min_val min(nums[i], min_val * nums[i])res max(res, max_val)return res416. 分割等和子集
题目描述
给定一个只包含正整数的非空数组判断是否可以将这些数字分成两个子集使得两个子集的元素和相等。
解题思路
转换01背包问题判断是否能找到一个子集其和等于总和的一半。01背包问题内循环反向遍历
Python代码
class Solution:def canPartition(self, nums: List[int]) - bool:n len(nums)s sum(nums)if s % 2 ! 0:return Falsetarget s // 2dp [False] * (target 1)dp[0] Truefor i in range(1, target 1):if nums[0] i:dp[i] Truefor i in range(1, n):# 01背包反向遍历for j in range(target, nums[i] - 1, -1):dp[j] dp[j] or dp[j - nums[i]]return dp[target]32. 最长有效括号
题目描述
给定一个只包含 ‘(’ 和 ‘)’ 的字符串找出最长有效格式正确且连续括号子串的长度。
解题思路
使用动态规划来解决。假设 dp[i] 表示以 i 结尾的最长有效括号的长度。状态转移方程根据当前字符和前一个字符的情况来判断。如果s[i]‘(’那么dp[i]一定是0 s[i] (的情况见代码中的注释。
Python代码
class Solution:# ((()))# 012345def longestValidParentheses(self, s: str) - int:n len(s)dp [0] * nres 0for i in range(1, n):if s[i] (:continue# 当前是), 前一个字符是(if s[i - 1] (:if i 1:dp[i] 2else:dp[i] dp[i-2] 2# 当前是), 前一个也是)那就需要判断s[i - 1 - dp[i-1]]是不是(是的话就能和当前的)匹配上elif i - 1 - dp[i-1] 0 and s[i - 1 - dp[i-1]] (:dp[i] dp[i-1] 2if i - 2 - dp[i-1] 0:dp[i] dp[i - 2 - dp[i-1]]res max(res, dp[i])return res
