NC34求路径

NC34求路径

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=188&&tqId=37383&rp=1&ru=/ta/job-code-high-week&qru=/ta/job-code-high-week/question-ranking

-3、 设计思想：

详细操作流程看下图：

-5、代码：
c++版本:

 class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
         int dp[110][110]={0};//定义一个dp[i][j]代表走到ij位置有几种方案
         for(int i = 0 ;i < m;i++) dp[i][0] =  1;//因为只能从上面一个方向来，所以初始化为1
         for(int j = 0 ;j < n;j++) dp[0][j] = 1;//因为只能从左面一个方向来，所以初始化为1
         for(int i = 1 ;i < m;i++)
         {
             for(int j = 1;j < n;j ++){
                 //对于普遍位置dp[i][j]就应该等于左边来和上边来的总和
                 dp[i][j] = dp[i-1][j]+dp[i][j-1];
             }
         }
        //返回右下角的值就是最终结果
         return dp[m - 1][n - 1];
    }
};

Java版本：