信息学竞赛题，小学组，你不一定会做！题目：小猫希望获得奖品的总值最大是多少？

小猫在玩一个淘宝游戏:在一个神奇的国度里，土地被划分成n×n的网格(1
≤n≤100)，每个格子里写有一个数x(1≤x≤100)，途径该格子的人会得到价 值x的奖品。现在小猫在左上角(1,1)，需要走到右下角(n,n)，他每一步只能向 右走一格或向下走一格。小猫希望获得奖品的总值最大，希望你能编程帮他解决 这个问题。
【输入文件】
文件名:walk.in。
第一行包含一个整数 n，表示网格的规模。
接下来 n 行，每行 n 个数，表示各个格子里的奖品价值。第 1 行第 1 个数表
示左上角，第 n 行第 n 个数表示右下角。
【输出文件】
文件名:walk.out。
仅包含一个整数，为小猫获得奖品的最大总价值。
【样例输入】
5
9 8 9 5 6
8 1 8 5 5
5 4 4 9 7
8 1 9 9 8
3 2 1 3 1
【样例输出】
66

这种题目对于小学生来说是比较难，不过对于成年人来说，没有难度。但是都发到网上代做，还有什么意义？

// Q717701.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "stdio.h"
#include "stdlib.h"

int solve(int x, int y, int * arr, int n)
{
    if (x == n - 1 && y == n - 1) return arr[x * n + y];
    if (x == n - 1) return solve(x, y + 1, arr, n) + arr[x * n + y];
    if (y == n - 1) return solve(x + 1, y, arr, n) + arr[x * n + y];
    int a = solve(x, y + 1, arr, n);
    int b = solve(x + 1, y, arr, n);
    return (a > b ? a : b) + arr[x * n + y];
}

int main()
{
    int n;
    scanf_s("%d", &n);
    int * arr = (int *)malloc(n * n * sizeof(int));
    for (int i = 0; i < n * n; i++)
        scanf_s("%d", &arr[i]);
    int r = solve(0, 0, arr, n);
    printf("%d\n", r);
    return 0;
}

我使用java写的，原谅我已经不会c了，所以输入的我都写死了，我自己测试了几组，还行，楼主可以自己转化为c的测试测试，不一定对，我是通过递归将所有种可能计算出来，然后存入列表比较谁大，所以当样本n为很大的时候，可能比较占内存。。。。。

package com.example.test;

import java.util.ArrayList;
import java.util.List;

public class cont {
    /*
     * x:横向坐标，从0开始
     * y:纵向坐标，从0开始
     * arr:n*n的样例
     * length:代表样例一边的个数，n
     * sum：记录每种走向的和
    */
    static List<Integer> ddSumList = new ArrayList<Integer>();

    //计算向右移动的总数
    public static void coutRight(int x,int y,int[][] arr,int length,int sum){
        if(x >= length){
            if(y >= length){
                //System.out.println("coutRight:"+sum);
                ddSumList.add(sum);
            }else{
                down(length-1,y+1,arr,length,sum);
            }
        }else{
            sum = sum + arr[x][y];
            //System.out.println("coutRight:"+sum);
            //每一步都有两种可能，一种向下，一种向右
            coutRight(x+1,y,arr,length,sum);
            coutDown(x,y+1,arr,length,sum);
        }
    }

    //这是计算一直向右，然后一直向下的特殊情况的方法
    public static void down(int x,int y,int[][] arr,int length,int sum){
        //System.out.println("coutDown-y:"+y);
        if(y >= length){
            //System.out.println("Down:"+sum);
            ddSumList.add(sum);
        }else{
            sum = sum + arr[x][y];
            down(length-1,y+1,arr,length,sum);
        }
    }

    //计算向下移动的总数
    public static void coutDown(int x,int y,int[][] arr,int length,int sum){
        if(y >= length){
            if(x >= length){
                //System.out.println("coutDown:"+sum);
                ddSumList.add(sum);
            }else{
                right(x+1,length-1,arr,length,sum);
            }
        }else{
            sum = sum + arr[x][y];
            //每一步都有两种可能，一种向下，一种向右
            //System.out.println("coutDown:"+sum);
            coutRight(x+1,y,arr,length,sum);
            coutDown(x,y+1,arr,length,sum);
        }
    }

    //这是计算一直向下，然后一直向右的特殊情况的方法
    public static void right(int x,int y,int[][] arr,int length,int sum){
        if(x >= length){
            //System.out.println("right:"+sum);
            ddSumList.add(sum);
        }else{
            sum = sum + arr[x][y];
            right(x+1,length-1,arr,length,sum);
        }
    }

    public static void main(String[] args) {
        int[][] numseven=new int[][]{{9,7,9,5,6},{8,1,8,9,5},{5,4,4,9,7},{8,1,9,9,8},{3,2,1,3,1}};
        //int[][] numseven=new int[][]{{9,8},{8,1}};
        coutRight(0,0,numseven,5,0);
        //coutDown(0,0,numseven,5,0);

        int maxSum = ddSumList.get(0);
        for (int i = 0; i < ddSumList.size()-1; i++) {
            if(maxSum < ddSumList.get(i+1)){
                maxSum = ddSumList.get(i+1);
            }
            //System.out.println(ddSumList.get(i));
        }
        System.out.println(maxSum);
    }
}