！！！题解 | 不同路径的数目(一) 写好了递推公式，剩下的就交给递归

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        /*
        也可以分为子问题，他最终到达了终点，可以是从左边向右移动来的，也可以是从上向下移动来的。所以f（M，N）等于F（M-1，N）+F（M，N-1）
        */
        //vector<vector<int>> res(m,vector<int>(n,0));
        int num=0;
       return func(m, n);

    }
    int func(int m,int n){
        /*
        if(right==(m-1)&&down==(n-1)){
            return 1;
        }
        int result=func(m, n, right+1, down)+func(m, n,right, down+1);
        return result;
        注意这段经典的错误，递归无法返回。
        func会一直进入right,但是由于down也需要等于N减一,所以始终无法返回
        */
        if(m==1||n==1)return 1;
        int x=0,y=0;
        if(m!=1)x=func(m-1, n);
        if(n!=1)y=func(m, n-1);
        return (x+y);
        /*
        if(m==1&&n==1)return 1;
        int x=0,y=0;
        if(m!=1)x=func(m-1, n);
        if(n!=1)y=func(m, n-1);
        return (x+y);
        这段代码也不太好,会超时,为什么呢?,因为这个地方要求，时间复杂度是N和M之间的较小值
        上段代码他必须要把N和M都走完之后才返回，但是情况是什么呢，只要M走完了，那么N就能确定了，剩下的就必须全走n；如果N走完了，那么剩下的路径就确定了，就是一直走M。（N为向右走，M向下走）所以只要其中一个达到边界，就可以返回。
        */
        //这样挺好,但是要注意,动态规划三步走:
        //第一找到递归子问题,也就是状态转移方程.
        //第二点,去掉重复的计算或搜索,也就是建立备忘录
        //第三,将递归转化为迭代
        //这样做一是没有明确这个函数它的准确定义,二是没有建立备忘录来记录可能会重复计算的结果,所以不太正确
    }
};