题解 | #求路径# 超详细动态规划算法分析

动态规划算法分析：  1.问题：求第一个点到最后一个点的路径数之和  2.状态定义：求(0,0)点到(i,j)点的路径数之和 3.状态转移方程：定义一个数组存储到每个点的路径数之和，因为只能向下或向右移动，所以点(i,j)的路经数之和numpath(i,j)=numpath(i-1,j)+numpath(i,j-1),但是第一行的元素和第一列的元素不满足这个方程，会造成数组越界  4.状态初始化：所以将第一行的元素和第二行的元素的路径和作为初始值，这样才可以递推出(i,j)元素的路径数之和  5.返回结果：numpath(m-1,n-1) 




public class NumberOfPaths {
    public static int uniquePaths(int m, int n) {
        int[][] numpath=new int[m][n];//存储到这个点的路径数之和
        if(numpath.length==0){
            return 0;
        }
        int i=0;
        int j=0;
        for( i=0;i<m;i++){
            numpath[i][0]=1;//第一行的元素作为初始值，到第一行每个元素的路径数都是1，因为不能向下又向上走
        }
        for( j=0;j<n;j++){
            numpath[0][j]=1;//第一列的元素作为初始值，到第一列每个元素的路径数都是1，因为不能向右又向左走
        }
        //从第二行第二列那个元素开始
        for( i=1;i<m;i++){
            for(j=1;j<n;j++){
                numpath[i][j]=numpath[i-1][j]+numpath[i][j-1];//numpath[i,j]的路径数之和是只能是他的左边一个元素的路径数之和加上他的上边一个元素的路径数之和
            }
        }
        return numpath[m-1][n-1];//返回最后一行最后一列元素的路径数之和
    }