有关dp问题的机器人走地图
今天俺和大佬交流的时候，发现了一个经典问题。就是机器人走方格问题~ 一开始没在意想到了杭电曾做过的一道题类似题当初俺是用打表的好像，回来之后细想这个跟那个好像不太一样~
题意：大概就是一个蜂巢状的图然后小蜜蜂只能向左或者向右，然后从一个小房子到另一个小房子会有多少条路！（因为数据小，所以我选择了打表）
思路：这不就是dp嘛！因为小蜜蜂若想到N，只能从N-1或者N-2 过来，那么我们就要求从小蜜蜂开始运动到N-1和N-2的路径之和。（当初想的竟然是递归找规律，amazing!） 代码如下：
include<bits/stdc++.h>
#define maxn 55
using namespace std;
int main(){
int n;
cin>>n;
long long f[maxn];
f[1] = 1;
f[2] = 2;
for(int i=3;i<=55;i++)
f[i] = f[i-1] + f[i-2];
while(n--){
int A,B;
cin>>A>>B;
cout<<f[B-A]<<endl;
}
return 0;
} 那么我们在来说说机器人这个题吧： 题意：M * N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。
思路：因为机器人是从（1,1)出发到（n,m），并且机器人也是只能向右或者向下走！
#include<bist/stdc++.h>
#define mod 1000000000+7
#define maxn 1052
using namespace std;
long long dp[maxn][maxn];
int main(){
int n,m;
while(cin>>n>>m){
memset(dp,0,sizeof(dp));
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(i == 1 && j == 1)
dp[i][j] = 1;
else
dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % mod
}
}
cout<<dp[n][m]<<endl;
}
return 0;
}然后俺想： 1.能否用DFS来实现呢？效率会不会比DP高？ 2.如果这个路上有的地方有障碍又该怎么来实现呢？！ 后续实现！
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-11-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读