有向无环图DAG
算法中有时称有向无环图为DAG ( Directed Acyclic Graph)。所谓有向无环图是指：任意一条边有方向，且不存在环路的图。有向无环图上的动态规划是学习动态规划的基础。很多问题都可以转化为DAG上的最长路、最短路或路径计数问题
DAG模型(固定终点的最长路和最短路)
硬币问题
题意：
- 有
种硬币，面值分别为
，每种都有无限多
给定非负整数，可以选用多少个硬币，使得面值之和恰好为
输出硬币数目的最小值和最大值分析：
将每种面值看作一个节点，设初始状态为
若当前在状态，每使用一个硬币
，状态便转移到
含义为：“从节点i出发到节点0的最长路径长度”(需要多少步)
路径长度是可以为
的(
表示这个d值还没有算过，初始化时也不能再把d全设为0，而要设置为一个负值令初始状态不合法，这里可以用
来表示没有算过，初始化时只需用
即可，同时
也要改成
但其实，由于结点
值表示“无法到达”，但在上述代码中，如果
如果把
初始化为
如果把的初值分开——只需把代码中
改为
即可
「在记忆化搜索中，如果用特殊值表示“还没算过”，则必须将其和其他的特殊情况（如无解）区分开，或者用一个标记数组标记此状态是否已经存在」
初始化
memset(vis,0,sizeof(vis));//标记数组 vis[0]=1; dpx[0]=0;记忆化搜索
int solve(int S)//搜索最少需要多少步 { if(vis[S])//是否已经找过此种状态 { return dpx[S]; } vis[S]=1; int &ans=dpx[S];//dpx[S]声明一个引用ans，这样任何对ans的读写实际上都是在对dpx[S]进行 ans=INF;//初始化到此状态无穷大 for(int i=1; i<=n; i++) { if(S>=v[i]) { ans=min(ans,solve(S-v[i])+1); } } return ans; }记忆化输出路径
void pint(int dp[ ],int S) { for(int i=1; i<=n; i++) { if(S>=v[i]&&(dp[S]==dp[S-v[i]]+1)) { printf("%d ",i); pint(dp,S-v[i]); break; } } }
