给一个h×m的网格,一开始在左上角 (1,1) 每一步只能向右或向下走,不能经过 '#' 格子,求走到右下角(h,m)有多少种走法。 ,请说出下列代码不能输出该问题正确结果的原因,并改正次代码,并且对每条语句进行注释
时间: 2024-02-24 20:57:18 浏览: 40
问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
5星 · 资源好评率100%
以下是有问题的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int dp[n+1]={0};//定义一个一维数组
dp[1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
if(x==1)
dp[j]=0;//如果有障碍物,将该格子的路径数设为 0
else
dp[j]+=dp[j-1];//状态转移方程
}
cout<<dp[m]<<endl;//输出答案
return 0;
}
```
代码的问题在于,定义的是一维数组 `dp`,但是在计算时却没有正确处理二维网格的行列关系。具体来说,`dp[j]` 表示的是从起点到第 i 行第 j 列的位置的不同路径数,但是在计算时却没有按照二维网格的行列关系来更新 `dp` 数组,而是直接把 `dp[j]` 当成了第 j 列的路径数,忽略了行的信息。因此,需要将 `dp` 数组的定义改为二维数组,并按照二维网格的行列关系来更新数组。
以下是改正后的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int dp[n+1][m+1]={0};//定义一个二维数组
dp[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
if(x==1)
dp[i][j]=0;//如果有障碍物,将该格子的路径数设为 0
else
dp[i][j]=dp[i-1][j]+dp[i][j-1];//状态转移方程
}
cout<<dp[n][m]<<endl;//输出答案
return 0;
}
```
这里将 `dp` 数组定义为二维数组,并按照二维网格的行列关系来更新数组。同时,将输出 `dp[n][m]`。
阅读全文