问题描述

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，可知此代码效率比上面的代码效率高，并且代码要比前者简单的多。

numberGame谈算法效率

问题描述

数据输入

数据输出