An example of the efficiency of digital game algorithm in C language is discussed

Recently I did a topic like this, which is very interesting ~ the topic is as follows:

Problem description

Winder recently played a Numbers game on an n by m grid with a number on each grid representing the value of that grid. Players need to go from the top left corner of the grid to the bottom right corner of the grid, can only go to the right or down, and can not go back. Players can choose whether to add the score value to the value of the grid after passing a grid, and the initial score of each game is 0.

Winder wants to know how many points he can get per game. However, Winder is very lazy, so you must help him to finish the job.

Data input

Enter the first row of two positive integers N and M (0) < N, M < = 15). And then we have N rows, M integers per row.

Data output

Output a row of integers representing the highest score that the game can achieve, sum. Make sure that sum is in the range of 32-bit integers.

The above problem is numberGame. Considering that each step has only two choices to the right and to the left, it is convenient to use the recursive algorithm. The code is as follows:

#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;
}

The code execution time is 46MS. Since the precursor of each node in the maximum weight path can only be the node above it or the node to its left (except the leftmost node), a one-dimensional array can be used to store the maximum weight of each node precursor, the code is as follows:

#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("%dn",dp[m]);   
}

This code USES a similar iterative algorithm, and the code execution time is 30MS, which shows that this code is more efficient than the above code, and the code is much simpler than the former.