网站手机版开发,京东的网站建设规划,三维立体网站建设,网站建设ppt演示文档文章目录 一、题目二、解法2.1 动态规划解法2.2 数论解法 三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法
2.1 动态规划解法 思路分析#xff1a;机器人只能向下或者向右移动#xff0c;那么到达可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法
2.1 动态规划解法 思路分析机器人只能向下或者向右移动那么到达i,j位置的路径和i-1,j以及(i,j-1)有关。那么我们就得到的动态规划的表达式 d p [ i ] [ j ] d p [ i − 1 ] [ j ] d p [ i ] [ j − 1 ] dp[i][j]dp[i-1][j]dp[i][j-1] dp[i][j]dp[i−1][j]dp[i][j−1]。其中因为到达第一行和第一列位置的路径只有一条因此dp数组中第一行第一列的元素都为1。根据如上信息我们写出如下代码。 程序如下
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(n, 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];}
};复杂度分析
时间复杂度 O ( m ∗ n ) O(m*n) O(m∗n)。空间复杂度 O ( m ∗ n ) O(m*n) O(m∗n)。 上述代码还可以再空间上进行压缩。从二维数组的角度来看i,j位置的路径数等于它上方的元素和左边的元素之和。如果省略掉上方的元素我们就能用一个一维数组来表示dp数组。迭代公式为 d p [ i ] d p [ i ] d o p [ i − 1 ] dp[i] dp[i]dop[i-1] dp[i]dp[i]dop[i−1]其中dop[i-1]代表左边元素公式右边旧的dp[i]代表上方元素。最终输出为dp[n-1]。
class Solution {
public:int uniquePaths(int m, int n) {vectorint dp(n);for (int i 0; i n; i) dp[i] 1;for (int j 1; j m; j) {for (int i 1; i n; i) {dp[i] dp[i - 1];}}return dp[n - 1];}
};复杂度分析
时间复杂度 O ( m ∗ n ) O(m*n) O(m∗n)。空间复杂度 O ( n ) O(n) O(n)。
2.2 数论解法 思路分析从数学上我们可以知道要到达终点每次又只能走一步那么总共需要的步数是 m n − 2 mn-2 mn−2那么有 m − 1 m-1 m−1步是要往下走的那么问题就变成了在 m n − 2 mn-2 mn−2步中 m − 1 m-1 m−1步往下走有多少种组合。这是一个组合问题。因此问题变成计算 C m n − 2 m − 1 ( m n − 2 ) ! ( m − 1 ) ! ( n − 1 ) ! ( m n − 2 ) ∗ . . . ( n 1 ) ∗ n ( m − 1 ) ! C_{mn-2}^{m-1}\frac{(mn-2)!}{{(m-1)!}{(n-1)!}}\frac{(mn-2)*...(n1)*n}{(m-1)!} Cmn−2m−1(m−1)!(n−1)!(mn−2)!(m−1)!(mn−2)∗...(n1)∗n。结合上述讨论我们写出如下代码。代码当中为了防止乘积中分子溢出我们首先使用long long类型并在循环中不断除以分母。 程序如下
class Solution {
public:int uniquePaths(int m, int n) {long long numerator 1; // 分子int denominator m - 1; // 分母int num1 m - 1, num2 m n - 2;while (num1--) {numerator * (num2--);while (denominator ! 0 numerator % denominator 0) { // 分母不能为0, 且分子要能整除分母numerator / denominator;denominator--;}}return numerator;}
};复杂度分析
时间复杂度 O ( m ) O(m) O(m)。空间复杂度 O ( 1 ) O(1) O(1)。
三、完整代码
# include iostream
# include vector
using namespace std;// 62、不同路径I
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(n, 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];}
};// 滚动数组削减空间复杂度
//class Solution {
//public:
// int uniquePaths(int m, int n) {
// vectorint dp(n);
// for (int i 0; i n; i) dp[i] 1;
// for (int j 1; j m; j) {
// for (int i 1; i n; i) {
// dp[i] dp[i - 1];
// }
// }
// return dp[n - 1];
// }
//};// 数论方法
//class Solution {
//public:
// int uniquePaths(int m, int n) {
// long long numerator 1; // 分子
// int denominator m - 1; // 分母
// int num1 m - 1, num2 m n - 2;
// while (num1--) {
// numerator * (num2--);
// while (denominator ! 0 numerator % denominator 0) { // 分母不能为0, 且分子要能整除分母
// numerator / denominator;
// denominator--;
// }
// }
// return numerator;
// }
//};int main() {int m 3, n 2;Solution s1;int result s1.uniquePaths(m, n);cout result endl;system(pause);return 0;
}end
