米粒和国际象棋棋盘问题

一道Exoweb面试题,由于明天去面试,找了找以前的题,发下我的做法.

问题如下：         在国际象棋的棋盘上面有 NxN个格。每个格里面有若干的米粒。一只小猪站在1x1的格里，小猪每次只能向高位的列或行移动。小猪会吃掉所经过的格子里面所有的米粒。请编写程序计算小猪能吃掉的米粒的最大值

对此问题，我第一个想法就是动态归划。
用M(i,j)表示i x j矩阵按照上述规则所得最大值，用V(i,j)表示NxN矩阵中i行j列的值，那么将有如下递归子结构

M(i,j) :
max{M(i-1,j),M(i,j-1)} + v(i,j)       i> 1 && j>1
M(i-1,j)  + v(i,j)                               j = 1,i !=1
M(i,j-1)  + v(i,j)                                i = 1,j != 1
v(i,j)                                       i == 1 && j == 1

用C语言实现的程序如下

#include<iostream>#include<string>using std::cout;int max(int a,int b){ return a>b?a:b;}int Matrix[4][4] = {2,2,3,0,0,3,1,1,1,2,2,1,4,1,2,2};int B[4][4];int findMaxSeq(int i,int j){if(i == 0&&j ==0){ B[0][0] = Matrix[0][0]; return B[0][0];}int left,up;left = i>0?findMaxSeq(i-1,j):0;up = j>0?findMaxSeq(i,j-1):0;B[j][i] = max(left,up) + Matrix[i][j];return B[j][i];}

若不需要路径的话,B矩阵可以省略,否则用矩阵B将M(i,j)的值存到B(j,i)中，以便找到吃米粒的路径。

void PathPrint(int i,int j){if(i == 0 && j == 0){ cout<<Matrix[0][0]<<" "; return;}int up = j > 0?B[i][j-1]:0;if(up == B[i][j] - Matrix[j][i]) PathPrint(i,j-1);else PathPrint(i-1,j);cout<<Matrix[j][i]<<" ";}int main(){cout<<"最大值为: "<<findMaxSeq(3,3)<<"/n"<<"路线: ";PathPrint(3,3);return 0;}