最近在刷动态规划的题目，跟着大佬“代码随想录”的pdf在刷力扣上的题目。碰到了一个动态规划的题目，于是将它记录了下来。
题目链接：https://leetcode-cn.com/problems/unique-paths/
我根据pdf学会了三种解题方法，分别是二叉树的遍历（把各个叶子节点找出），动态规划（二维数组的优点是思路清楚，一目了然。一维数组的优点是大大减少了空间复杂度），数论（组合的方法，不过要注意int类型相乘的时候会溢出，要做到边乘边除）。
? 下面我来详细的叙述各种方法，并附上代码
题目如图所示：
?首先我要讲述的是二叉树的遍历的方法，这里的知识需要用的数据结构。没学数据结构的童鞋请参考B站《王道考研数据结构》。不说了上代码
class Solution { public: int dfs(int i,int j,int m,int n){ if(i>m||j>n)return 0;//这一步不能缺省 if(i==m&&j==n)return 1;//递归的边界 else return dfs(i+1,j,m,n)+dfs(i,j+1,m,n); } int uniquePaths(int m, int n) { return dfs(1,1,m,n); } };
这里由于要遍历整个叶子节点，时间复杂度将是指数的形式，故不可取。
第二种方法是动态规划，首先我们讲解用二维数组的方法来动态规划。
最近在“代码随想录”pdf里面学到了动态规划五部曲
1.确定dp数组
2.确定递推公式
3.边界的初始化
4.确定遍历顺序
5.举例推导dp数组
?那么我们先来看动态规划（二维数组的实现）
class Solution {
public:
int uniquePaths(int m, int n) {
//创建dp[m][n],代表走到第m行,n列的所有路径
vector<vector<int>>dp(m,vector<int>(n,0));
//初始化边界
for(int i=0;i<m;i++)dp[i][0]=1;
for(int j=0;j<n;j++)dp[0][j]=1;
//通过递推公式初始化数组的其它元素
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};我们再来试着用动态规划（一维数组的实现），实际上就是把二维数组的j省略了
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int>dp(m);
//这里相当于J=0时的初始化
for(int i=0;i<m;i++){
dp[i]=1;
}
for(int j=1;j<n;j++){
for(int i=1;i<m;i++){
dp[i]+=dp[i-1];
}
}
return dp[m-1];
}
};那么最后我们看看数论（排列组合的方法）：从m+n-2个数中选m-1个数
组合数公式如图
?
class Solution {
public:
int uniquePaths(int m, int n) {
int numerator=1;
int demunator=1;
int count=m-1;
int t=m+n-2;
while(count--)numerator*=(t--);
for(int i=1;i<=m-1;i++)demunator*=i;
return numerator/demunator;
}
};?
?但是这种方法提交的话会出现“溢出”（两个int类型相乘）
Line 8: Char 25: runtime error: signed integer overflow: 1764322560 * 10 cannot be represented in type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:17:25?解决方法是做到边乘边除。
class Solution {
public:
int uniquePaths(int m, int n) {
long long numerator = 1; // 分?
int denominator = m - 1; // 分?
int count = m - 1;
int t = m + n - 2;
while (count--) {
numerator *= (t--);
while (denominator != 0 && numerator % denominator == 0) {
numerator /= denominator;
denominator--;
}
}
return numerator;
}
};?好了，终于把这道题叙述完了。
已知乾坤大，犹怜草木青。这里北风，星河辽阔，一路相伴。
?