- 1、题目描述:
-3、 设计思想:
详细操作流程看下图:
-4、视频讲解链接B站视频讲解
-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版本:
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here int [][]dp = new int [m][n];//定义一个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]; } }
Python版本:
# # # @param m int整型 # @param n int整型 # @return int整型 # class Solution: def uniquePaths(self , m , n ): # write code here dp = [[0 for i in range(n)] for i in range(m)] #定义一个dp[i][j]代表走到ij位置有几种方案 for i in range(m): dp[i][0] = 1 #因为只能从上面一个方向来,所以初始化为1 for j in range(n): #因为只能从左面一个方向来,所以初始化为1 dp[0][j] = 1 for i in range(1,m): for j in range(1,n): #对于普遍位置dp[i][j]就应该等于左边来和上边来的总和 dp[i][j] = dp[i-1][j] + dp[i][j-1] #返回右下角的值就是最终结果 return dp[m-1][n-1]