代码随想录算法训练营第36期DAY42

DAY42

62不同路径

AC了，舒服！待会看看优质解答。

1. class Solution {
2. public:
3.     int uniquePaths(int m, int n) {
4.         vector<vector<int>> dp(m,vector<int>(n,1));
5.         for(int i=0;i<m;i++){
6.             for(int j=0;j<n;j++){
7.                 if(i!=0&&j!=0){
8.                     dp[i][j]=dp[i][j-1]+dp[i-1][j];
9.                 }
10.             }
11.         }
12.         return dp[m-1][n-1];
13.     }
14. };

代码随想录题解：

1. 图论深搜法：将路径化为到叶子的路。输出叶子结点的数量。这里主要学习深搜写法和思想：

1. class Solution {
2. public:
3.     int dfs(int i,int j, int m,int n){
4.         if(i>m||j>n) return 0;
5.         if(i==m&&j==n) return 1;
6.         return dfs(i+1,j,m,n)+dfs(i,j+1,m,n); 
7.     }
8.     int uniquePaths(int m, int n) {
9.         return dfs(1,1,m,n);
10.     }
11. };

1. 动态规划与自己写的一致
2. 数论方法：

这里学习计算组合问题的模版，针对组合数C：

1. class Solution {
2. public:
3.     //数论方法
4.     int uniquePaths(int m, int n) {
5.         long long fenzi=1;
6.         int fenmu=m-1;
7.         int count=m-1;
8.         int fenzistart=m+n-2;
9.         while(count--){
10.             fenzi*=(fenzistart--);
11.             while(fenmu!=0&&fenzi%fenmu==0){
12.                 fenzi/=fenmu;
13.                 fenmu--;
14.             }
15.         }
16.         return fenzi;
17.     }
18. };

附上做的笔记：

DAY42

62不同路径

AC了，舒服！待会看看优质解答。

1. class Solution {
2. public:
3.     int uniquePaths(int m, int n) {
4.         vector<vector<int>> dp(m,vector<int>(n,1));
5.         for(int i=0;i<m;i++){
6.             for(int j=0;j<n;j++){
7.                 if(i!=0&&j!=0){
8.                     dp[i][j]=dp[i][j-1]+dp[i-1][j];
9.                 }
10.             }
11.         }
12.         return dp[m-1][n-1];
13.     }
14. };

代码随想录题解：

1. 图论深搜法：将路径化为到叶子的路。输出叶子结点的数量。这里主要学习深搜写法和思想：

1. class Solution {
2. public:
3.     int dfs(int i,int j, int m,int n){
4.         if(i>m||j>n) return 0;
5.         if(i==m&&j==n) return 1;
6.         return dfs(i+1,j,m,n)+dfs(i,j+1,m,n); 
7.     }
8.     int uniquePaths(int m, int n) {
9.         return dfs(1,1,m,n);
10.     }
11. };

1. 动态规划与自己写的一致
2. 数论方法：

这里学习计算组合问题的模版，针对组合数C：

1. class Solution {
2. public:
3.     //数论方法
4.     int uniquePaths(int m, int n) {
5.         long long fenzi=1;
6.         int fenmu=m-1;
7.         int count=m-1;
8.         int fenzistart=m+n-2;
9.         while(count--){
10.             fenzi*=(fenzistart--);
11.             while(fenmu!=0&&fenzi%fenmu==0){
12.                 fenzi/=fenmu;
13.                 fenmu--;
14.             }
15.         }
16.         return fenzi;
17.     }
18. };

附上做的笔记：

63不同路径ii

想对了，但是还差一点点：思维、手写模拟（别懒）、语法（多练多写多想）

不会做，卡在状态转移了：如果左边和上面都是0，显然是走不过来的，该怎么表示呢？

“有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了”这一点倒是做到了。

手写模拟，多画图！初始化：x轴和y轴，障碍物之后的格子都是0了。写for一旦obstacle就退出循环了，那么其他的就是保持初始值0. 还有：如果ob为1，那么就continue 不去计算它的dp（能保持加0）

写一遍：

1. class Solution {
2. public:
3.     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
4.         vector<vector<int>> dp(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),0));
5.         //起点/终点有障碍 0；
6.         if(obstacleGrid[0][0]==1||obstacleGrid[obstacleGrid.size()-1][obstacleGrid[0].size()-1]==1) return 0;
7.         for(int i=0;i<obstacleGrid.size()&&obstacleGrid[i][0]!=1;i++) dp[i][0]=1;
8.         for(int i=0;i<obstacleGrid[0].size()&&obstacleGrid[0][i]!=1;i++) dp[0][i]=1;
9.         for(int i=1;i<obstacleGrid.size();i++){
10.             for(int j=1;j<obstacleGrid[0].size();j++){
11.                 if(obstacleGrid[i][j]==1) continue;
12.                 dp[i][j]=dp[i-1][j]+dp[i][j-1];
13.             }
14.         }
15.         return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
16.     }
17. };

细节：从1开始循环。