经典算法面试题（三）（小猪吃米）经典算法面试题（三）：小猪

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

文章图片
chess.png

分析：
假设小猪从(0,0)开始到棋盘上任一点(m,n)所能吃到的最多米粒数为f(m,n)，则f(m,n)满足下列关系式：
f(m,n)=max{f(m,n-1), f(m-1,n)} + Matrix[m][n];

注意:
f(0,j) = f(0, j-1) + matrix[0][j], 0<=j<=N-1
f(i,0) = f(i-1, 0) + matrix[i][0], 0<=i<=N-1
上面分析的思路实际上是典型的动态规划思路。

源程序：

#include #define MAX(a, b) ((a > b) ? a : b) #define N 4int matrix[N][N] = {{2,2,3,0}, {0,3,1,1}, {1,2,2,1}, {4,1,2,2}}; int count[N][N]; // 初始化小猪在第0行或第0列所有位置所能吃到的最大米粒数 void initialize() { count[0][0] = matrix[0][0]; for(int i=1; i < 4; i++) { count[0][i] = count[0][i-1] + matrix[0][i]; count[i][0] = count[i-1][0] + matrix[i][0]; } }// 找出所能吃到的最大的米粒数 int find_max (int i, int j) { if(0 == i) { return count[0][j]; } else if(0 == j) { return count[i][0]; }int count1 = find_max (i, j-1); int count2 = find_max (i-1, j); count[i][j] = matrix[i][j] + MAX (count1, count2); return count[i][j]; }// 打印出小猪吃米的完整路径 void print_path (int i, int j) { if ( i >= 0 && j >= 0 ) { if(count[i][j] == count[i-1][j] + matrix[i][j]) { print_path (i-1, j); } else if(count[i][j] == count[i][j-1] + matrix[i][j]) { print_path (i, j-1); }if(N - 1 == i && N - 1 == j) { printf ("(%d,%d)", i, j); } else { printf ("(%d,%d)->", i, j); } } }// 打印出小猪走到矩阵中任一点所能吃到的最大米粒数 void print (void) { for(int i = 0; i < 4; ++i) { for(int j = 0; j < 4; ++j) { printf ("%d\t", count[i][j]); } printf ("\n"); } }int main (void) { initialize (); int max = find_max(3, 3); printf("count = %d\n", max); print(); printf("\nThe path is:\n"); print_path(3, 3); putchar('\n'); return 0; }

运行结果：