-
题目：
从一个m*n的矩阵的左上角[0，0]走到右下角[m-1，n-1]有几条路径？ -
思路：
1.DFS：O(2^(m+n-1))：大概算一下，矩阵中几乎每个位置都是由上或左两个方向到达，从而进行一次递归，因此总的递归次数肯定是2的指数次，指数差不多为矩阵总格子数，造成超时；空间主要为递归时栈的开销；
class Solution {
private:
//相当于一棵二叉树
int dfs(int i, int j, int m, int n) {
if (i > m || j > n) return 0;//出界
if (i == m && j == n) return 1;//到达右下角
return dfs(i, j + 1, m, n) + dfs(i + 1, j, m, n);//去寻找
}
public:
int uniquePaths(int m, int n) {
return dfs(1, 1, m, n);
}
};
2.DP：O(mn)：两层for循环，O(mn)：一个m*n大小的二维数组，用于存dp更新结果
动规五部曲来分析：
①确定dp数组（dp table）以及下标的含义
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
②确定递推公式
想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。
那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
③dp数组的初始化
如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
所以初始化代码为：
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
④确定遍历顺序
这里要看一下递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
⑤举例推导dp数组
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n));//dp[i][j]表示从[0][0]到达[i][j]的路径数;
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 - 1][j] + dp[i][j - 1];//只能向下和向右走
}
}
return dp[m - 1][n - 1];//到达目标位置的路径数
}
};
3.优化DP：①dp数组更新时，只跟左边位置和上边位置的值有关，因此可用一维数组记录即可；②上面都是按行更新，但m和n具体谁更大是不确定的，因此，可将方法2的空间优化为O(min(m，n))
class Solution {
public:
//若想优化空间为min(m, n)，需要根据m和n的大小进入两个不同分支，下面代码就不写了
int uniquePaths(int m, int n) {
vector<int> dp(n);//dp[i]表示从[0][0]到达[i][j]的路径数;
for (int i = 0; i < n; ++i) dp[i] = 1;//第一行初始化为1
for (int i = 1; i < m; ++i) {//当前一维dp数组更新到第i行
for (int j = 1; j < n; ++j) {//对于第i行，从左往右更新dp数组
dp[j] += dp[j - 1];//dp[j - 1]相当于从左边来的，dp[j]相当于从上边来的
}
}
return dp[n-1];//到达目标位置的路径数
}
};
4.最优解数论:O(min(m，n))，O(1）
从左上角到右下角的过程中，我们需要移动 m+n-2 次，在这m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么时候向下走。
那么有几种走法呢？可以转化为，给你m + n - 2个不同的数，随便取m - 1个数，有几种取法。那么这就是一个组合问题了。当然选择n-1个数的位置也可以，因为本质上例如C3，1 == C3，2
class Solution {
public:
int uniquePaths(int m, int n) {
long long numerator = 1; // 分子
int Minm_n = min(m, n); //最优化:例如求C8,3而不是C8，5
int denominator = Minm_n - 1; // 分母
int count = Minm_n - 1;
int t = m + n - 2;
while (count--) {
numerator *= (t--);//能整除分母再除，否则先暂时乘分子
while (denominator != 0 && numerator % denominator == 0) {
numerator /= denominator;
denominator--;
}
}
return numerator;
}
};
- 总结：
方法2，3：DP的空间优化问题，dp更新式需要哪些变量，就只保存并更新那些变量
方法4：求组合数，要注意①溢出问题 ②整除问题