大致题意为：从上游到下游有很多游船停靠站点。姑且设定为StopStation（0）（这个站点为起始站点），StopStation（1），StopStation（2）......每个站点自上而下分

布。其中，每两个站点之间的行驶费用是不同的。现在问如果从StopStation（0）起始点，坐船到下游最后一个站点，那么，求出花费的最小代价。

      这个问题的求解主要依靠动态规划。而动态规划是从下而上的算法基础。

                          0    (i=j)

   f[i,j](min)=

                          f[i,k](min) +f[k,j](min) （k<j)

      f[i,j](min)表示从站点i到j的最小费用。通过公式，很容易进行想到 利用同样的公式再次求解f[i,k](min)，f[k,j](min)。然后就像剥香蕉一样，一层一层往里面剥。所以，当求

得最底层数之后，再重新往上层一次一次遍回溯，从而求得最终 f[i,j](min)最小费用。

     

1 #include
     
       2 using namespace std; 3 const int Max = 100; 4 //// 5  6 //利用动态规划，自底向上，参照矩阵乘法开销最小问题 7  8 /// 9 int nn[Max][Max],rr[Max][Max],money[Max][Max];              //rr[Max][Max]记录两站点之间花费，如rr[i][j]表示站点i到j站点之间的花费10 int i,j,k,m;11 void PrintMoney(int rr[Max][Max],int mm[Max][Max],int nn)   12 { 13   int MoneyMin=0;                                          //先将MoneyMin初始化为014 15   for(i=0;i
      
       < j+i;k++)                             28        {29          if(MoneyMin > rr[j][k]+rr[k][j+i])  30              MoneyMin = rr[j][k]+rr[k][i+j];               //确定公式中k的最佳位置，即MoneyMin值为最小时31 32          rr[j][j+i] = MoneyMin;                            //确定了站点j到站点j+i的最小花费（由于是自底向上计算，所以总是从用最小值去求较大区间的最小值33        }34      }35   }36   return ;37 }38 39 40 int main()41 {42 int n,a;43 while(cin>>n)44 {45  if(n==0)46    break;47  else48  {49    for(i=0;i
       
        >a;53         rr[i][j] = a;54        }55 56  }57 PrintMoney(money,rr,n);  58 cout<
       
      
     

      输入时，用 

               for(i=0;i<n;i++)

                         for(j=i+1;j<=n;j++)

      每行数字分别表示表示：S[0]~S[1],S[2]....S[n],

                                     S[1]~S[2].....S[n],

                                     S[2]~S[3]......S[n] 之间的花费。

     最后一行表示结果从S[0]到S[3]的最小花费。

     数据结果：

     

         引用请注明出处，谢谢合作！