LC62题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
这个很好想，公式d[m,n]=d[m-1,n]+d[m,n-1];
//第一种解法 超时
class Solution {
public:
int uniquePaths(int m, int n) {
//d[m,n]=d[m-1,n]+d[m,n-1];
int res=0;
if(m>1&&n>1)
res=uniquePaths(m-1,n)+uniquePaths(m,n-1);
else
res=1;
return res;
}
};
因为超时，我就找了个数组记录计算结果，AC后的结果
这里传二维数组失败，又传了vector
class Solution {
public:
// int tmp1=0;
// int tmp2;
void count(vector< vector<int> > &rec,int m,int n,int a,int b){
int res=0;
if(m>1&&n>1){
if(rec[m-1][n]==0){
count(rec,m-1,n,a,b);
if(m-1<=b&&n<=a){
rec[n][m-1]=rec[m-1][n];
}
}
if(rec[m][n-1]==0){
count(rec,m,n-1,a,b);
if(n-1<=a&&m<=b){
rec[n-1][m]=rec[m][n-1];
}
}
rec[m][n]=rec[m-1][n]+rec[m][n-1];
}
else{
rec[m][n]=1;
}
}
int uniquePaths(int m, int n) {
//d[m,n]=d[m-1,n]+d[m,n-1];
vector< vector<int> > rec;
for(int i=0;i<m+1;i++){
vector<int> tmpr;
for(int j=0;j<n+1;j++){
tmpr.push_back(0);
}
rec.push_back(tmpr);
}
count(rec,m,n,m,n);
return rec[m][n];
}
};
实际上，直接填数组就可以了TAT
但是动态规划还是注意一下填数组的顺序，这里用的都是填过的数，有的时候用的不一定是填过的数字
int uniquePaths(int m, int n) {
//d[m,n]=d[m-1,n]+d[m,n-1];
int rec[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0||j==0){
rec[i][j]=1;
}else{
rec[i][j]=rec[i-1][j]+rec[i][j-1];
}
}
}
return rec[m-1][n-1];
// return rec[m][n];
}
LC63题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//差不多，看是否有1.
int a=obstacleGrid.size();
int b=obstacleGrid[0].size();
if(obstacleGrid[a-1][b-1]==1){
return 0;
}
int k=-1;
long long rec[a][b];
memset(rec,0,sizeof(rec));
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
if(obstacleGrid[i][j]==1){
rec[i][j]=0;
}else if(i==0||j==0){
// 看路中是不是有1
if(i==0&&j>0){
rec[i][j]=rec[i][j-1];
}
else if(j==0&&i>0){
rec[i][j]=rec[i-1][j];
}else {
rec[i][j]=1;
}
}else{
rec[i][j]=rec[i-1][j]+rec[i][j-1];
}
}
}
return rec[a-1][b-1];
}
};
以上这种必须把返回数组定义为long类型，否则中间值会产生int溢出
另一种（我看有js这样写的，但是C++写就超时）
int count(vector<vector<int>>& obstacleGrid,int i,int j){
int res=0;
if(obstacleGrid[i][j]==1)
return res;
else if(i==0||j==0){
if(i==0&&j>0){
res=count(obstacleGrid,i,j-1);
}
else if(j==0&&i>0){
res=count(obstacleGrid,i-1,j);
}else {
res=1;
}
}else{
res=count(obstacleGrid,i,j-1)+count(obstacleGrid,i-1,j);
}
return res;
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//差不多，看是否有1.
int a=obstacleGrid.size();
int b=obstacleGrid[0].size();
int res=count(obstacleGrid,a-1,b-1);
return res;
}
题目LC64
LC63稍微改一下可做LC64的题解
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
//差不多，看是否有1.
int a=grid.size();
int b=grid[0].size();
long long rec[a][b];//记录结果
memset(rec,0,sizeof(rec));
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
if(i==0||j==0){
// 看路中是不是有1
if(i==0&&j>0){
rec[i][j]=rec[i][j-1]+grid[i][j];
}
else if(j==0&&i>0){
rec[i][j]=rec[i-1][j]+grid[i][j];
}else {
rec[i][j]=grid[i][j];
}
}else{
if(rec[i-1][j]>rec[i][j-1])
rec[i][j]=rec[i][j-1]+grid[i][j];
else
rec[i][j]=rec[i-1][j]+grid[i][j];
}
}
}
return rec[a-1][b-1];
}
};
网友评论