有向無環(huán)圖DAG
算法中有時稱有向無環(huán)圖為DAG ( Directed Acyclic Graph)。所謂有向無環(huán)圖是指：任意一條邊有方向，且不存在環(huán)路的圖。

有向無環(huán)圖上的動態(tài)規(guī)劃是學習動態(tài)規(guī)劃的基礎。很多問題都可以轉(zhuǎn)化為DAG上的最長路、最短路或路徑計數(shù)問題

DAG模型(固定終點的最長路和最短路)

硬幣問題

題意：

• 有 種硬幣，面值分別為，每種都有無限多
  給定非負整數(shù) ，可以選用多少個硬幣，使得面值之和恰好為？
  輸出硬幣數(shù)目的最小值和最大值

分析：

• 將每種面值看作一個節(jié)點，設初始狀態(tài)為，目標狀態(tài)為0
  若當前在狀態(tài) ，每使用一個硬幣，狀態(tài)便轉(zhuǎn)移到
  含義為：“從節(jié)點i出發(fā)到節(jié)點0的最長路徑長度”(需要多少步)

• 路徑長度是可以為的(本身可以是)，所以不能再用表示這個d值還沒有算過，初始化時也不能再把d全設為0，而要設置為一個負值令初始狀態(tài)不合法，這里可以用 來表示沒有算過，初始化時只需用即可，同時 也要改成

• 但其實，由于結(jié)點不一定真的能到達結(jié)點，所以需要用特殊的值表示“無法到達”，但在上述代碼中，如果根本無法繼續(xù)往前走，返回值是，將被誤以為是“已到達終點”的意思

• 如果把初始化為呢？但代表“還沒算過”，所以返回相當于放棄了自己的勞動成果
  如果把初始化為一個很大的整數(shù)，從目前來看，它也會被認為是“還沒算過”，但至少可以和所有的初值分開——只需把代碼中改為即可

「在記憶化搜索中，如果用特殊值表示“還沒算過”，則必須將其和其他的特殊情況（如無解）區(qū)分開，或者用一個標記數(shù)組標記此狀態(tài)是否已經(jīng)存在」

初始化

memset(vis,0,sizeof(vis));//標記數(shù)組
vis[0]=1;
dpx[0]=0;

記憶化搜索

int solve(int S)//搜索最少需要多少步
{
   if(vis[S])//是否已經(jīng)找過此種狀態(tài)
   {
       return dpx[S];
   }
   vis[S]=1;
   int &ans=dpx[S];//dpx[S]聲明一個引用ans，這樣任何對ans的讀寫實際上都是在對dpx[S]進行
   ans=INF;//初始化到此狀態(tài)無窮大
   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;
       }

   }
}