网站建设小程序南宁,英文网站定制公司,福州公关公司,海外营销网站建设动态规划理论基础 动态规划#xff0c;英文#xff1a;Dynamic Programming#xff0c;简称DP#xff0c;如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。 区别 动态规划中每一个状态一定是由上一个状态推导出来的#xff0c;这一点就区分于贪心… 动态规划理论基础 动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。 区别 动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的 例子 动态规划中dp[j]是由dp[j-weight[i]]推导出来的然后取max(dp[j], dp[j - weight[i]] value[i])而贪心呢每次拿物品选一个最大的或者最小的就完事了和上一个状态没有关系所以贪心解决不了动态规划的问题 知道动规是由前一个状态推导出来的而贪心是局部直接选最优的对于刷题来说就够用了 动规五部曲 确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 509. 斐波那契数 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 提醒 很简单的动规入门题但简单题使用来掌握方法论的用动规五部曲来分析。 一、动态规划 class Solution:def fib(self, n: int) - int:# 排除 Corner Caseif n 0:return 0# 创建 dp table dp [0] * (n 1)# 初始化 dp 数组dp[0] 0dp[1] 1# 遍历顺序: 由前向后。因为后面要用到前面的状态for i in range(2, n 1):# 确定递归公式/状态转移公式dp[i] dp[i - 1] dp[i - 2]# 返回答案return dp[n] 二、递归 class Solution:def fib(self, n: int) - int:if n 2:return nreturn self.fib(n - 1) self.fib(n - 2) 70. 爬楼梯 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 提醒 本题先自己想一想 之后会发现和 斐波那契数 有点关系。 class Solution:def climbStairs(self, n: int) - int:if n 1:return ndp [0] * (n 1)dp[1] 1dp[2] 2for i in range(3, n 1):dp[i] dp[i - 1] dp[i - 2]return dp[n] 思考 这道题目还可以继续深化就是一步一个台阶两个台阶三个台阶直到 m个台阶有多少种方法爬到n阶楼顶。 这又有难度了这其实是一个完全背包问题但力扣上没有这种题目大家可以去卡码网去做一下 57. 爬楼梯 746. 使用最小花费爬楼梯 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 提醒 明确说 第一步是不用花费的 class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:dp [0] * (len(cost) 1)dp[0] 0 # 初始值表示从起点开始不需要花费体力dp[1] 0 # 初始值表示经过第一步不需要花费体力for i in range(2, len(cost) 1):# 在第i步可以选择从前一步i-1花费体力到达当前步或者从前两步i-2花费体力到达当前步# 选择其中花费体力较小的路径加上当前步的花费更新dp数组dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])return dp[len(cost)] # 返回到达楼顶的最小花费
