1. 前置知识
（1）动态规划表就是装递归返回值的容器
（2）动态转移方程等价于递归中的尝试策略
（3）递归中各 if 判断条件就是尝试策略的分类，对应了动态转移方程
（4）想象一个二叉树，递归（记忆化）是从顶到底，顶可分出多种情况，而到底就是结束，不会再有分类，因此是从复杂到简单。dp是从底到顶，从最简单的情况入手，当简单情况全部推完，再逐步向复杂情况，因为简单的情况都是复杂情况的分支。
（5）如何判断顶和底，是从前往后还是从后往前，实际是去判断是如何依赖的。dp是从被依赖向依赖的方向填，递归相反。
2. 题目链接
https://leetcode.cn/problems/minimum-cost-for-tickets/description/https://leetcode.cn/problems/minimum-cost-for-tickets/description/
3. 递归（记忆化）版本
int n,l[5]={0,1,7,30},cost[5],days[400],mem[400];
//主函数调用dfs(1)
int dfs(int dep) //dep是记录哪一天旅行的数组的下标
{
int i,k,ans=0x3f3f3f3f;
if (dep>n) //边界条件
return 0;
if (mem[dep]!=0) //返回记忆值
return mem[dep];
for (k=1,i=dep;k<=3;k++)
{
while (i<=n && days[dep]+l[k]>days[i])
i++;
ans=min(ans,cost[k]+dfs(i)); //递归取最小值
}
return mem[dep]=ans;
}
· dfs中核心片段分析
for (k=1,i=dep;k<=3;k++)
{
while (i<=n && days[dep]+l[k]>days[i])
i++;
ans=min(ans,cost[k]+dfs(i));
}1. 这里就是尝试策略，k代表第几个策略（ 1 / 7 / 30天）。
2. 由于是递归版本，旅行第一天的决策会影响后面所有决策，因此循环从1开始往后，从顶到底。
3. · k=1，只管days [ dep ] 这一天，i 一直往后找下一次旅行是在哪一天，对应的days中的下标。
· k=7，管从days [ dep ] 这一天往后六天，若days中从dep下标往后对应的数值包含在这里面就跳过，直到除了范围。i 一直往后找下一次旅行是在哪一天，对应的days中的下标。
· k=30 同理
4. 尤其注意任何判断条件中都必须包含边界条件，不能越界！
4. dp 版本
dp[n+1]=0;
for (i=n;i>0;i--)
{
j=i;
for (k=1;k<=3;k++)
{
while (j<=n && days[i]+l[k]>days[j])
j++;
dp[i]=min(dp[i],cost[k]+dp[j]);
}
}
cout<<dp[1];1. 状态转移方程结构与上述递归版本完全一致，印证了动态转移方程就是尝试策略。
2. ans = min ( ans , cost [ k ] + dfs ( i ) ) 变为 dp [ i ] = min ( dp [ i ] , cost [ k ] + dp [ j ] )，印证了动态规划表就是装递归返回值的容器。
3. 思考 是如何判断顶和底（复杂与易）的
想象一棵树，根节点是旅行第一天，每个节点向下分三支，对应三种决策，直到叶节点，就是旅行最后一天，因此猜想从后往前。
再换个角度来看，最简单的是旅行最后一天，只需要考虑自己，后面已经没有了。而不断的往前推，每一个点后面的天数就越多，越复杂。而dp本质就是记录子问题去解决大问题，显而易见是从后往前填答案，最后输出dp [ 0 ]。
5. 总结
无论是递归还是dp，核心都在于找到尝试策略分类，实质是在模拟。dp只是递归的另一种写法，两者并无本质区别。
6. 完整代码
（1）递归版文章来源：https://www.toymoban.com/news/detail-846214.html
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,l[5]={0,1,7,30},cost[5],days[400],mem[400];
int dfs(int dep)
{
int i,k,ans=0x3f3f3f3f;
if (dep>n)
return 0;
if (mem[dep]!=0)
return mem[dep];
for (k=1,i=dep;k<=3;k++)
{
while (i<=n && days[dep]+l[k]>days[i])
i++;
ans=min(ans,cost[k]+dfs(i));
}
return mem[dep]=ans;
}
int main()
{
int i;
cin>>n;
for (i=1;i<=n;i++)
cin>>days[i];
for (i=1;i<=3;i++)
cin>>cost[i];
cout<<dfs(1);
return 0;
}（2）dp版文章来源地址https://www.toymoban.com/news/detail-846214.html
int main()
{
int i,j,k;
int dp[400];
cin>>n;
memset(dp,0x3f,sizeof(dp)); //这个预处理非常重要，否则后面的min全都是0
for (i=1;i<=n;i++)
cin>>days[i];
for (i=1;i<=3;i++)
cin>>cost[i];
dp[n+1]=0; //basecase
for (i=n;i>0;i--)
{
j=i;
for (k=1;k<=3;k++)
{
while (j<=n && days[i]+l[k]>days[j])
j++;
dp[i]=min(dp[i],cost[k]+dp[j]);
}
}
cout<<dp[1];
return 0;
}到了这里，关于动态规划（一）：从递归转变为dp ——力扣 983 最低票价的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
