[数据结构与算法]动态规划——不同路径

?

?一、数学方式

从m+n-2格中选出m-1个向下的格

Java:

class Solution {
    public int uniquePaths(int m, int n) {
        long steps=1;//注意这里的类型
        for(int x=n,y=1;y<m;x++,y++){
            steps=steps*x/y;
        }
        return (int)steps;//这里需要类型转换
    }
}

?

二、动态规划，分解问题

f[i][j]=f[i-1][j]+f[i]f[j-1]? ?如果是边界格（0行、0列）的话，则只有一种路径，则设为1.

Java:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f=new int[m][n];
        for(int i=0;i<m;i++){
            f[i][0]=1;
        }
        for(int j=0;j<n;j++){
            f[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }
}

C++:?注意这里用vector来实现二维数组。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m,vector<int>(n));//二维数组
        for(int i=0;i<m;i++){
            f[i][0]=1;
        }
        for(int j=0;j<n;j++){
            f[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }
};

?