专栏首页ypw递归,递推以及动态规划总结

递归,递推以及动态规划总结

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

然后前不久做题又遇到了,人家题解可以用递归,递推跟DP,以及DFS+记忆化搜索来解决,让我感悟颇深!!

题意:有个n*m的迷宫,有三种字母。R代表只能向右走,D代表只能向下走,B代表上下都可以走。迷宫最上角为(1,1),迷宫右下角为(n,m),问有多少种不同的移动路线能走出去,结果对1e9+7取余

思路:迷宫问题,我首先想到的时DFS,但仔细一想感觉好像DP啊

DFS+记忆化搜索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll dp[55][55];
char mp[55][55];
int n,m;
ll dfs(int x,int y)
{
	if(x<0||y<0||x>=n||y>=m) return 0;
	if(dp[x][y]) return dp[x][y];
	
	if(x==n-1&&y==m-1)
	{
		return 1;
	}
	if(mp[x][y]=='R') return dp[x][y]=dfs(x,y+1)%mod;
	if(mp[x][y]=='D') return dp[x][y]=dfs(x+1,y)%mod;
	if(mp[x][y]=='B') return dp[x][y]=(dfs(x+1,y)%mod+dfs(x,y+1)%mod)%mod;
}
int main()
{
	cin >>n>>m;
	for(int i=0;i<n;i++)
	{
		cin >>mp[i];
	}
	dfs(0,0);
	cout <<dp[0][0]%mod<<endl;
}

题解的意思时这样的: 经典的走格子DP(棋盘型DP)。 然后就是只要从左上角开始for,如果是D就往下累加,如果是R就往右累加,如果是B就同时累加。

题解:递归

#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
const long long mod=1e9+7;
int n,m;
char s[MAXN][MAXN];
long long dp[MAXN][MAXN];
long long dp_dfs(int x,int y)
{
    if(x>n||y>m)return 0;
    if(dp[x][y]!=-1)return dp[x][y];
    if(s[x][y]=='D')return dp[x][y]=dp_dfs(x+1,y);
    if(s[x][y]=='R')return dp[x][y]=dp_dfs(x,y+1);
    if(s[x][y]=='B')return dp[x][y]=(dp_dfs(x+1,y)+dp_dfs(x,y+1))%mod;
}
int main()
{
    scanf("%d %d",&n,&m);
    memset(dp,-1,sizeof(dp));
    dp[n][m]=1;
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s[i]+1);
    }
    printf("%lld\n",dp_dfs(1,1));
    return 0;
}

题解:递推

#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const int MAXN=55;
long long dp[MAXN][MAXN];
char mp[MAXN][MAXN];
int n,m;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",mp[i]+1);
    }
    dp[1][1]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(mp[i][j]=='D')
            {
                dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
            }
            if(mp[i][j]=='R')
            {
                dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
            }
            if(mp[i][j]=='B')
            {
                dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
                dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
            }
        }
    }
    printf("%lld\n",dp[n][m]);
    return 0;
}

那么我来总结一下: 递推就是迭代,从前到后。 递归是系统堆栈,实现函数自身调用,有一个最终的出口。从后往前然后在回来返回计算值。

所以递推的效率要高一点,在可能的情况下应尽量使用递归。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 有关dp问题的机器人走地图

    今天俺和大佬交流的时候,发现了一个经典问题。就是机器人走方格问题~ 一开始没在意想到了杭电曾做过的一道题类似题当初俺是用打表的好像,回来之后细想这个跟那个好像...

    用户7727433
  • 2017 年ICPC 中国大陆区域赛铜牌题解

    题意:有n只猫m条鱼,然后每只猫吃鱼的速度不同,为ci,,,然后吃完当前鱼可以继续吃下一条,问经过x分钟后还剩下几只完整的鱼几只不完整的鱼。

    用户7727433
  • 购物

    在遥远的东方,有一家糖果专卖店。 这家糖果店将会在每天出售一些糖果,它每天都会生产出m个糖果,第i天的第j个糖果价格为C[i][j]元。 现在的你想要在接下...

    用户7727433
  • 【kAri OJ】621. 廖神的树

    廖神和男神在植树节的时候准备玩一个奇怪的游戏,他们现在有一个被分割成n*n个格子的矩形土地,他们现在准备往这个地里种树,但这个种树游戏必须满足以下两个要求:

    饶文津
  • Leetcode 91 Decode Ways

    A message containing letters from A-Z is being encoded to numbers using the fol...

    triplebee
  • LeetCode 72. Edit Distance

    ShenduCC
  • 《剑指offer》第25天:最简单的动态规划

    这种思想的本质是:一个规模比较大的问题(可以用两三个参数表示的问题),可以通过若干规模较小的问题的结果来得到的(通常会寻求到一些特殊的计算逻辑,如求最值等),如...

    程序员小浩
  • 每日算法系列【LeetCode 115】不同的子序列

    一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 ...

    godweiyang
  • 程序员面试金典 - 面试题 17.13. 恢复空格(DP+Trie树)

    哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。 像句子"I reset the computer. It still didn’...

    Michael阿明
  • P2051 [AHOI2009]中国象棋

    题目描述 这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大...

    attack

扫码关注云+社区

领取腾讯云代金券