专栏首页ypw有关dp问题的机器人走地图

有关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.如果这个路上有的地方有障碍又该怎么来实现呢?! 后续实现!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HPU 18级个人积分赛--first

    J. Worker 思路:我们仔细分析一下题意,给了n个厂,m个人,假设每个厂的福利原因使得工人的工作能力不同,然后你要把这m个人分给n个厂,使得每个厂的总效...

    用户7727433
  • 递归,递推以及动态规划总结

    在我的映像里面,当初第一次结束DP的时候,总感觉跟递归还是递归好像!以至于我混淆了他们。

    用户7727433
  • 最快最简单的排序---桶排序

    是不是很好理解,就是开一个比最大数据大或者等于的一个数组,然后相应的桶遇到数就++,最后输出就行了。

    用户7727433
  • POJ 2192 Zipper HDU 2059 龟兔赛跑

    owent
  • 牛客国庆集训派对Day6 E-Growth(离散化DP)

    链接:https://ac.nowcoder.com/acm/contest/206/E

    ACM算法日常
  • P1156 垃圾陷阱

    题目描述 卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方,它的深度为D(2<=D<=100)英尺...

    attack
  • 漫画:动态规划系列 第三讲

    在上一篇中,我们了解了什么是DP(动态规划),并且通过DP中的经典问题 "最大子序和",学习了状态转移方程应该如何定义。在本节中,我们将沿用之前的分析方法,通过...

    程序员小浩
  • 【CodeForces 567F】Mausoleum

    1到n每个数字有两个,排成先不降后不升的序列,比如112332,并且满足k个形如 3 <= 6 代表第三个数字要≤第六个数字这样的约束要求,求有多少种排法。

    饶文津
  • 19 nowcoder 第二场 经典dp延伸,单调队列变量维护 H Second Large Rectangle

    题意: n*m大小的矩形 n,m<1000。 s[ i ][ j ] 只包含 0 和 1,求 只包含1 的第二大矩形面积。

    用户2965768
  • HPU 18级个人积分赛--first

    J. Worker 思路:我们仔细分析一下题意,给了n个厂,m个人,假设每个厂的福利原因使得工人的工作能力不同,然后你要把这m个人分给n个厂,使得每个厂的总效...

    用户7727433

扫码关注云+社区

领取腾讯云代金券