DAG上的动态规划「二」

有向无环图DAG
算法中有时称有向无环图为DAG ( Directed Acyclic Graph)。所谓有向无环图是指：任意一条边有方向，且不存在环路的图。

有向无环图上的动态规划是学习动态规划的基础。很多问题都可以转化为DAG上的最长路、最短路或路径计数问题

DAG模型(固定终点的最长路和最短路)

硬币问题

题意：

• 有 种硬币，面值分别为，每种都有无限多
  给定非负整数 ，可以选用多少个硬币，使得面值之和恰好为？
  输出硬币数目的最小值和最大值

分析：

• 将每种面值看作一个节点，设初始状态为，目标状态为0
  若当前在状态 ，每使用一个硬币，状态便转移到
  含义为：“从节点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;
       }

   }
}