leetcode931最短下降路径

 　　一个中等难度的 dp 题目，矩阵的长宽决定了问题规模的大小。问题的定义是在矩阵 A 中一层一层的下降，这个定义本身便具有最优子结构性质。

　　我们在第 i 层想要下降到 i+1 层有三种选择，走左边 j-1 ，走中间 j ，走右边 j+1 ，我们取三者的最小值即可。

　　设 G( i，j ) 为计算 从坐标 i，j 下降的最小路径，状态转移方程为：G( i，j ) = Min{ G( i+1，j )+A[ i ][ j ] , G( i+1，j -1 )+A[ i ][ j -1 ] , G( i+1，j +1)+A[ i ][ j +1 ] }.

　　回归条件为落到最后一层下面，此时路径和为 0。

    public int minFallingPathSum(int[][] A) {
        int[][] cache=new int[A.length+1][A.length+1];
        int re=Integer.MAX_VALUE;
        for(int i=0;i<A.length;i++){
            int temp=minFallingPathSum(A,0,i,cache);
            re=Math.min(re,temp);
        }
        return re;
    }

    public int minFallingPathSum(int[][] A, int x, int y, int[][] cache) {
        int length = A.length;
        if (x == length) {
            return 0;
        }
        if (cache[x][y] != 0) {
            return cache[x][y];
        }
        int[] nums = A[x];
        int re = nums[y] + minFallingPathSum(A, x + 1, y, cache);
        if (y - 1 >= 0) {
            re = Math.min(re, nums[y - 1] + minFallingPathSum(A, x + 1, y - 1, cache));
        }
        if (y + 1 < length) {
            re = Math.min(re, nums[y + 1] + minFallingPathSum(A, x + 1, y + 1, cache));
        }
        cache[x][y] = re;
        return re;
    }

　　效率：