一道算法题、解决方案

一道算法题、！
int number[5][5]={22,32,14,77,45,0,12,34,37,23,0,0,44,23,15,0,0,0,34,54,0,0,0,0,88};
排列方式如下、

从最左上角开始往右或往右下走，所经过的值总和最大，求出总值和经过的那条的线路，用java实现


[解决办法]
java淡忘了
[解决办法]
有个问题，能往下吗？如果不能往下，那么只有从开始就直接往右下了，否则怎么能到终点？
如果只是5*5的数组的话，可以考虑全排，找出最大的。
[解决办法]
这也属于动态规划吧。
[解决办法]
简单写了段代码，通过递归取所有可能路径，然后排序取出和最大的一条路径

Java code

import java.util.*;public class Test {        static class DataNode { //定义一个类用于记录数组元素的位置的值        int x, y, value;        public DataNode(int x, int y, int value) {            this.x = x;            this.y = y;            this.value = value;        }    }    static class DataList implements Comparable<DataList> { //定义一个类用于记录路径        int sum = 0;        List<DataNode> nodes = new ArrayList<DataNode>();        public DataList() {}        public void addNode(DataNode node) {            nodes.add(0, node);            sum += node.value;        }        public int compareTo(DataList dl) {            return dl.sum - sum;        }    }    public static void main(String[] args) throws Throwable {        int[][] number={            {22,32,14,77,45},            {0,12,34,37,23},            {0,0,44,23,15},            {0,0,0,34,54},            {0,0,0,0,88}};        List<DataList> result = findAll(number, 0, 0); //获取所有路径        if (result.size() > 0) {            Collections.sort(result); //降序排序所有路径            //for (DataList dl : result) {            DataList dl = result.get(0); //取出第一条路径（该路径权值最大）                System.out.printf("sum=%d\n", dl.sum);                for (DataNode n : dl.nodes) {                    System.out.printf("(%d,%d:%d), ", n.x, n.y, n.value);                }                System.out.println();            //}        }    }    //定义一个递归寻找所有路径的方法    public static List<DataList> findAll(int[][] number, int x, int y) {        if (number==null || number.length==0 || number[0].length==0) {            return new ArrayList<DataList>(); //非法数据的时候返回0元素的集合        }        List<DataList> result = new ArrayList<DataList>();        if (x==number.length-1 && y==number[0].length-1) { //路径走到终点的时候递归结束            DataList dl = new DataList();            dl.addNode(new DataNode(x, y, number[x][y]));            result.add(dl);            return result;        }        if (x < number.length && y < number[0].length) { //右下有效时递归取右下路径集合            List<DataList> tmp = findAll(number, x+1, y+1);            for (DataList dl : tmp) { //在递归获取的子集合中追加当前元素                dl.addNode(new DataNode(x, y, number[x][y]));             }            result.addAll(tmp); //把右下方的子集合路径追加到最终的结果集中        }        if (y < number[0].length) { //右方有效时递归取右方路径集合            List<DataList> tmp = findAll(number, x, y+1);            for (DataList dl : tmp) { //同上                dl.addNode(new DataNode(x, y, number[x][y]));            }            result.addAll(tmp);        }        if (x < number.length) { //下方有效时递归取下方有效集合            List<DataList> tmp = findAll(number, x+1, y);            for (DataList dl : tmp) { //同上                dl.addNode(new DataNode(x, y, number[x][y]));            }            result.addAll(tmp);        }        return result;    }}
[解决办法]
数可以为负数没