62. 不同路径

1.递归（超时）

第一眼想到递归回溯，因为只有两种路径，向下或者向右，但是大网格的时候超出时间限制，因为其包含了大量的压栈出栈重复计算，代码

class Solution {
        int res = 0;

        public int uniquePaths(int m, int n) {
            //x,y 0 0 xmac m ymax x
            getCount(0, 0, m, n);
            return res;
        }

        private void getCount(int x, int y, int m, int n) {
            if (x >= m || y >= n) {
                return;
            }

            if (x == m - 1 || y == n - 1) {
                res++;
                return;
            }

            //向右
            if (x < m - 1) {
                x++;
                getCount(x, y, m, n);
                x--;
            }


            //向下
            if (y < n - 1) {
                y++;
                getCount(x, y, m, n);
                y--;
            }

        }
    }

2.动态规划

如图所示一个7*3的网格

思路：

• 每个点的结果由其上一个结点的可能的路径决定
• 上边界只会是起点一直向右走到达的，因此路径只有1种
• 左边界只会是起点一直向下走达到的，因此路径也只有1种
• 其他情况右其上方结点或者左侧结点决定

class Solution {
        int res = 0;

        public int uniquePaths(int m, int n) {
            int[][] data=new int[m][n];
            for (int i = 0; i < m; ++i) {
                data[i][0]=1;
            }

            for (int i = 0; i < n; ++i) {
                data[0][i]=1;
            }
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    data[i][j]=data[i-1][j]+data[i][j-1];
                }
            }

            return data[m-1][n-1];
        }
    }