企业做网站的费用如果做账,做网站销售好做吗,网站建设要学会编程吗,wordpress怎么备份数据库下面的例子不错#xff1a; 对于动态规划#xff0c;能学到不少东西#xff1b;
你要清楚每一步都在做什么#xff0c;划分细致就能够拆解清楚#xff01; xk. - 力扣#xff08;LeetCode#xff09;
labuladong的算法笔记-动态规划-CSDN博客 动态规划是…下面的例子不错 对于动态规划能学到不少东西
你要清楚每一步都在做什么划分细致就能够拆解清楚 xk. - 力扣LeetCode
labuladong的算法笔记-动态规划-CSDN博客 动态规划是一种强大的算法设计策略用于解决具有重叠子问题和最优子结构特点的问题。在面对动态规划类题目时遵循以下步骤可以帮助你系统地解决问题 1. 定义状态 确定变量识别哪些变量会影响问题的解。例如在背包问题中关键变量可能是物品的重量和价值以及剩余的背包容量。状态表示用这些变量定义状态。例如dp[i][w] 可能表示前i个物品放入容量为w的背包所能获得的最大价值。 2. 状态转移方程 建立关系找到状态之间的关系即如何从一个状态转移到另一个状态。这通常涉及到一个递推公式。例如在斐波那契数列中F(n) F(n-1) F(n-2)。边界条件确定递推公式的起始状态通常是最简单的情况例如 dp[0][w] 0背包问题中没有物品时的价值。 3. 选择方向 自底向上从最简单的状态开始逐步构建更复杂的状态。这种方法通常使用循环实现避免了重复计算。自顶向下从复杂的状态开始递归地解决子问题。这种方法通常使用递归和记忆化memoization来避免重复计算。 4. 初始化 初始状态根据问题的性质初始化DP数组。例如所有状态初始化为0或无穷大。 5. 计算 填充DP表根据状态转移方程填充DP表或数组。确保按正确的顺序填充以便在计算每个状态时所需的前驱状态已经被计算。 6. 返回结果 解析答案DP过程完成后根据问题要求解析出最终答案。这可能是DP表中的某个特定值也可能是回溯整个DP过程找到最优解的具体方案。 7. 复杂度分析 时间复杂度通常由状态的数量和状态转移的复杂度决定。空间复杂度由存储状态所需的空间决定可以通过滚动数组等方式优化空间复杂度。 1 70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 示例 1 输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶这是一个简单的动态规划的问题 分解问题不积硅步无以至千里 假设当前到了第x层,并且小于x层的走法f(x)我们都知道。 那么后面如何求呢 第一个阶梯、第二个阶梯都是1下就能走到y x1,那么 fy f(y-1) f(y-2), 想要上到第y步 一定是从前面阶梯走过来的。 class Solution:def climbStairs(self, n: int) - int:dp [1] * (n1)for i in range(2,n1):dp[i] dp[i-1] dp[i-2]#print(dp)return dp[n] 2 198. 打家劫舍 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 相邻不能同时偷 示例 1 输入[1,2,3,1]
输出4
解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。 在做这一个题目的时候 f(x): 到第x个房间能得到的最大收益 我也是设定加入到了第X个房间那么之前的状态到房间能得到的最大收益我都是知道的。所以f(X1) 怎么做才能最大呢 怎么能偷到x1个房子由x-1过来的x-2过来的开始我没考虑到这点。 class Solution:def rob(self, nums: List[int]) - int:dp nums[::]for i in range(2,len(nums)):temp dp[i-2]if i-30:temp max(temp,dp[i-3])dp[i] temp nums[i]return max(dp) 3 322. 零钱兑换 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1 输入coins [1, 2, 5], amount 11
输出3
解释11 5 5 1 递归动态规划 有硬币【q,w,e】 思想 比如7个硬币怎么使用最少的硬币进行组合呢 f(7) min(f(7-q),f(7-w),f(7-e)) 1 还有个特殊条件 f(7-q),f(7-w),f(7-e) 存在组合基石不然无法站住脚 我这个思路不是特征的好。 class Solution:def coinChange(self, coins: List[int], amount: int) - int:if amount0:return 0 coins sorted(coins)dp [0] * (amount1)for i in range(amount1):for coin in coins:if i-coin0:dp[i] 1elif i-coin0:if dp[i]0:# if dp[i-coin]0:dp[i]0else:dp[i] dp[i-coin] 1 #min(, dp[i])else:if dp[i-coin]0:dp[i]0else:dp[i] min(dp[i-coin] 1, dp[i])else:breakprint(dp)return -1 if dp[amount]0 else dp[amount]# def sub_x(amount):# if amount0:# return 0# if amount 0 or amountcoins[0]:# return -1# temp -1# for coin in coins:# x sub_x(amount - coin) # -1, 0# if x -1:# continue# if temp-1:# temp x1# else:# temp min(x1, temp)# return tempreturn sub_x(amount) 思路二 陈奕迅的背包 class Solution:def coinChange(self, coins: List[int], amount: int) - int:n len(coins)dp [[amount1] * (amount1) for _ in range(n1)] # 初始化为一个较大的值如 inf 或 amount1# 合法的初始化dp[0][0] 0 # 其他 dp[0][j]均不合法# 完全背包套用0-1背包【遍历硬币数目k】for i in range(1, n1): # 第一层循环遍历硬币for j in range(amount1): # 第二层循环遍历背包for k in range(j//coins[i-1]1): # 第三层循环当前硬币coin取k个 (k*coinamount)dp[i][j] min( dp[i][j], dp[i-1][j-k*coins[i-1]] k )ans dp[n][amount] return ans if ans ! amount1 else -1
