站长工具爱站网免登录直接玩的游戏

站长工具爱站网,免登录直接玩的游戏,徐州关键字优化咨询,刷单网站建设动态规划入门 文章目录动态规划入门动态规划的概念dp的重点必须存在 “重叠子问题”必须满足 “最优子结构”状态定义与状态转移方程例子动态规划的解题步骤例题动态规划的概念 动态规划#xff08;Dynamic Programming#xff0c;DP#xff09;#xff1a;是一种求解多阶段…动态规划入门文章目录动态规划入门动态规划的概念dp的重点必须存在 “重叠子问题”必须满足 “最优子结构”状态定义与状态转移方程例子动态规划的解题步骤例题动态规划的概念动态规划Dynamic ProgrammingDP是一种求解多阶段决策过程最优化问题的方法。在动态规划中通过把原问题分解为相对简单的子问题先求解子问题再由子问题的解而得到原问题的解。动态规划是一种解决多阶段决策最优化问题的算法思想核心逻辑是将复杂问题分解为若干个重叠的子问题通过存储子问题的最优解避免重复计算最终推导出原问题的最优解。dp的重点其中的一些要点:必须存在 “重叠子问题”原问题拆解后的子问题会重复出现而非一次性求解后不再使用。如果子问题无法复用,那我们的dp数组就是空占地方的无效数组,对优化没有任何帮助.必须满足 “最优子结构”原问题的最优解必然由其某个子问题的最优解推导而来子问题的最优解是原问题最优解的 “组成部分”。不然dp数组中的值就无法使用,我们可以通过数学归纳法来证明最优子结构的存在.状态定义与状态转移方程描述 “当前状态如何由前一个 / 几个状态推导而来” 的数学表达式转移方程必须 “无后效性”即当前状态的推导只依赖已确定的前序状态不依赖未确定的后续状态状态一旦确定其值就固定不变不受后续决策的影响例子假设你是商店收银员现在需要给顾客找5 元零钱手头的硬币面值只有三种1元、2元、5元硬币数量无限。要求用最少的硬币数凑出 5 元怎么凑我们用dp[i]表示凑出 i 元零钱需要的最少硬币数。比如dp[1] 凑 1 元需要的最少硬币数对于每个金额i从 1 到 5我们可以尝试用每一种硬币面值coin1、2、5如果coin i硬币面值不大于当前金额才能用这枚硬币那么凑i元的思路是先凑出i - coin元再加上 1 枚coin面值的硬币我们要选所有可能中硬币数最少的所以转移方程是dp[i] mindp[i - 1] 1dp[i - 2] 1dp[i - 5] 1#includestdio.h#includestdlib.hintmin(inta,intb){returnab?a:b;}intmain(){inttarget5;intcoins[]{1,2,5};intcoinCountsizeof(coins)/sizeof(coins[0]);int*dp(int*)malloc((target1)*sizeof(int));if(dpNULL)return1;dp[0]0;for(inti1;itarget;i){dp[i]99999;}for(inti1;itarget;i){for(intj0;jcoinCount;j){intcoincoins[j];if(coinidp[i-coin]!99999){dp[i]min(dp[i],dp[i-coin]1);}}}return0;}动态规划的解题步骤定义状态明确 dp [i]或 dp [i][j]、dp [i][j][k]代表什么必须具体、无歧义确定边界条件初始化最小子问题的解如 dp [0]、dp [1]避免递推时数组越界或逻辑错误推导状态转移方程核心步骤找到 “当前状态” 与 “前序状态” 的关系计算最终结果通过迭代推荐或递归 记忆化从边界条件递推到原问题的解。例题力扣983.最低票价在一个火车旅行很受欢迎的国度你提前一年计划了一些火车旅行。在接下来的一年里你要旅行的日子将以一个名为days的数组给出。每一项是一个从1到365的整数。火车票有三种不同的销售方式一张为期一天的通行证售价为costs[0]美元一张为期七天的通行证售价为costs[1]美元一张为期三十天的通行证售价为costs[2]美元。通行证允许数天无限制的旅行。 例如如果我们在第2天获得一张为期 7 天的通行证那么我们可以连着旅行 7 天第2天、第3天、第4天、第5天、第6天、第7天和第8天。返回你想要完成在给定的列表days中列出的每一天的旅行所需要的最低消费。intdata[3]{1,7,30};intmincostTickets(int*days,intdaysSize,int*costs,intcostsSize){int*dp(int*)malloc((daysSize1)*sizeof(int));for(inti0;idaysSize;i){dp[i]9999;}dp[daysSize]0;for(intidaysSize-1;i0;i--){for(intk0;k3;k){intji;while(jdaysSizedata[k]days[i]days[j]){j;}inttempcosts[k]dp[j];if(tempdp[i]){dp[i]temp;}}}returndp[0];}力扣42.接雨水给定n个非负整数表示每个宽度为1的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。intmax(inta,intb){returnab?a:b;}intmin(inta,intb){returnab?b:a;}inttrap(int*height,intheightSize){if(heightSize2){return0;}intl[heightSize],r[heightSize];l[0]height[0];for(inti1;iheightSize;i){l[i]max(l[i-1],height[i]);}r[heightSize-1]height[heightSize-1];for(intiheightSize-2;i0;i--){r[i]max(r[i1],height[i]);}intans0;for(inti1;iheightSize-1;i){ansmax(0,min(l[i-1],r[i1])-height[i]);}returnans;}