硬币收集問題

問題描述：

 在一個mxn的矩陣中A，每個舉證單元存放着一定數量（A(i,j)>=0）的硬币，假設有一個小機器人，它從舉證的左上角A(0,0)開始，每經過一個單元格就收集其中的所有硬币，并且隻能向右走或者往下走，問它從左上角一直到右下角A(m,n)，能夠收集最多的硬币是多少？

例如，以2x3的簡單矩陣為例：

小機器人如果按照路徑：(0,0)->(0,1)->(1,1)->(1,2)的路徑走的話，可以收集到最多的硬币數：21。

分析：

由于該問題對每一步所走路徑的方向有确定的限制：隻能是向右走或者是向下走，實際上尋找其遞推式是很簡單的。

實作：

package agdp;
public class CollectionCoins {
    private static int[][] initData(int m,int n){
        int[][] ary = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ary[i][j] = (int)(Math.random()*10);//随機生成[0,10]的整數
            }
        }
        return ary;
    } 
    public static int getMostCoins(int[][] ary){
        int m = ary.length,n = ary[0].length;
        int[][] aux = new int[m+1][n+1];//aux第0行和第0列均置0，充當哨兵作用
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                //遞推式
                aux[i][j] = Math.max(aux[i-1][j], aux[i][j-1])+ary[i-1][j-1];
            }
        }
        return aux[m][n];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int m = 3,n = 4;
        int[][] ary = initData(m,n);
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print(ary[i][j]+"-");
//            }
//            System.out.println();
//        }
        int result = getMostCoins(ary);
        System.out.print(result);
    }
}