动态规划入门
动态规划入门
文章目录
- 动态规划入门
- 动态规划的概念
- dp的重点
- 必须存在 “重叠子问题”
- 必须满足 “最优子结构”
- 状态定义与状态转移方程
- 例子
- 动态规划的解题步骤
- 例题
动态规划的概念
动态规划（Dynamic Programming，DP）：是一种求解多阶段决策过程最优化问题的方法。在动态规划中，通过把原问题分解为相对简单的子问题，先求解子问题，再由子问题的解而得到原问题的解。
动态规划是一种解决多阶段决策最优化问题的算法思想，核心逻辑是：将复杂问题分解为若干个重叠的子问题，通过存储子问题的最优解，避免重复计算，最终推导出原问题的最优解。
dp的重点
其中的一些要点:
必须存在 “重叠子问题”
原问题拆解后的子问题会重复出现，而非一次性求解后不再使用。
如果子问题无法复用,那我们的dp数组就是空占地方的无效数组,对优化没有任何帮助.
必须满足 “最优子结构”
原问题的最优解，必然由其某个子问题的最优解推导而来（子问题的最优解是原问题最优解的 “组成部分”）。
不然dp数组中的值就无法使用,我们可以通过数学归纳法来证明最优子结构的存在.
状态定义与状态转移方程
描述 “当前状态如何由前一个 / 几个状态推导而来” 的数学表达式
转移方程必须 “无后效性”：即当前状态的推导，只依赖已确定的前序状态，不依赖未确定的后续状态；状态一旦确定，其值就固定不变，不受后续决策的影响
例子
假设你是商店收银员，现在需要给顾客找5 元零钱，手头的硬币面值只有三种：
1元、2元、5元（硬币数量无限）。要求：用最少的硬币数凑出 5 元，怎么凑？
我们用
dp[i]表示：凑出 i 元零钱需要的最少硬币数。比如：dp[1] = 凑 1 元需要的最少硬币数；
对于每个金额
i（从 1 到 5），我们可以尝试用每一种硬币面值coin（1、2、5）：
如果
coin <= i（硬币面值不大于当前金额，才能用这枚硬币），那么凑i元的思路是：先凑出i - coin元，再加上 1 枚coin面值的硬币；我们要选所有可能中硬币数最少的，所以转移方程是：
dp[i] = min（dp[i - 1] + 1，dp[i - 2] + 1，dp[i - 5] + 1）
#include<stdio.h>#include<stdlib.h>intmin(inta,intb){returna<b?a:b;}intmain(){inttarget=5;intcoins[]={1,2,5};intcoinCount=sizeof(coins)/sizeof(coins[0]);int*dp=(int*)malloc((target+1)*sizeof(int));if(dp==NULL)return1;dp[0]=0;for(inti=1;i<=target;i++){dp[i]=99999;}for(inti=1;i<=target;i++){for(intj=0;j<coinCount;j++){intcoin=coins[j];if(coin<=i&&dp[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((daysSize+1)*sizeof(int));for(inti=0;i<daysSize;i++){dp[i]=9999;}dp[daysSize]=0;for(inti=daysSize-1;i>=0;i--){for(intk=0;k<3;k++){intj=i;while(j<daysSize&&data[k]+days[i]>days[j]){j++;}inttemp=costs[k]+dp[j];if(temp<dp[i]){dp[i]=temp;}}}returndp[0];}
力扣42.接雨水
给定
n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。intmax(inta,intb){returna>=b?a:b;}intmin(inta,intb){returna>=b?b:a;}inttrap(int*height,intheightSize){if(heightSize<=2){return0;}intl[heightSize],r[heightSize];l[0]=height[0];for(inti=1;i<heightSize;i++){l[i]=max(l[i-1],height[i]);}r[heightSize-1]=height[heightSize-1];for(inti=heightSize-2;i>=0;i--){r[i]=max(r[i+1],height[i]);}intans=0;for(inti=1;i<heightSize-1;i++){ans+=max(0,min(l[i-1],r[i+1])-height[i]);}returnans;}