最近做了這樣一個題目，感覺挺有趣~題目如下：
問題描述
Winder 最近在玩一個數字游戲，該游戲是在一個n*m 的網格上進行的，每個格子上有 一個數字，代表這個格子的數值。玩家需要從網格的左上角的格子走到右下角的格子，每次 只能向右或者向下走，并且不能回頭。玩家每經過一個格子可以選擇分值是否加上該格子的 數值，每次游戲的初始分數都是0。
Winder 想知道在每場游戲，他最多能夠得到多少分值。但是，Winder 很懶，所以你必 須幫他來完成這件事。
數據輸入
輸入第一行兩個正整數N 和M（0<N、M<=15）。 接下來有N 行，每行M 個整數。
數據輸出
輸出一行一個整數，表示該場游戲能取得的最高分數sum。（保證sum 在32 位整數范圍 內）。
上面這個問題就是numberGame，考慮到每一步都有且只有向右和向左兩個選擇，故用遞歸算法會很方便，代碼如下：
#include<stdio.h>
#include<iostream>
#include<windows.h>
#pragma comment(lib,"winmm.lib")
using namespace std;
int j=0;
int go(int kc,int *Ac,int wc,int nc)
{
if(kc>=j) return wc;
if(kc<j)
{
if((kc+1)%5==0)
return go(kc+nc,Ac,Ac[kc]+wc,nc);
else
return go(kc+1,Ac,Ac[kc]+wc,nc)>go(kc+nc,Ac,Ac[kc]+wc,nc)?go(kc+1,Ac,Ac[kc]+wc,nc):go(kc+nc,Ac,Ac[kc]+wc,nc);
}
}
void main()
{
int m,n;
DWORD t1, t2;
cin>>m>>n;
int *A,i,w=0;
A=new int [m*n];
for(i=0;i<m*n;i++)
{
if(i!=0&&i%n==0)cout<<endl;
cin>>A[i];
}
j=m*n;
t1=timeGetTime();
int max=go(0,A,w,n);
cout<<max;
t2=timeGetTime();
cout<<"the time it takes:"<<t2-t1;
}
代碼執行時間為46MS，由于最大權值路徑上每個節點的前驅只能是其上方的節點或其左邊的節點（最左的節點除外），故可用一個一維數組存儲每個節點前驅的最大權值，代碼如下：
#include<stdio.h>
int i,j,dp[16],n,m,v;
void main(){
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=1;j<=m;j++){
scanf("%d",&v);
if(dp[j]<dp[j-1])dp[j] = dp[j-1];
dp[j]+= v>0?v:0;
}
printf("%d/n",dp[m]);
}
此代碼用了類似迭代的算法，代碼執行時間為30MS，可知此代碼效率比上面的代碼效率高，并且代碼要比前者簡單的多。
