AcWing 2067. 走方格(看了豁然开朗的14行代码动态规划)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 2067. 走方格(看了豁然开朗的14行代码动态规划) 原题链接简单

作者：

蓝桥杯冲ya , 2020-09-28 21:13:44 , 所有人可见 , 阅读 2692

14

5

一开始直接 dfs 竟然会TLE，思考一会后简单动态规划搞定QAQ
思路：假如当前行列都不为偶数的话，即当前方案数等于上边和左边方案数之合

#include<iostream>
using namespace std;
int n,m;
int dp[35][35];
int main()
{
    cin>>n>>m;
    dp[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(i%2!=0||j%2!=0)
                dp[i][j]+=dp[i-1][j]+dp[i][j-1];
    cout<<dp[n][m];
}

再来个TLE dfs 版本吧，也能水分数呜呜呜

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int st[32][32],dx[2]={0,1},dy[2]={1,0};
bool book[32][32];
int n,m,ans,ss;
void dfs(int x,int y)
{
    if(x>n||y>m)return;
    if(x==n&&y==m)ans++;
    for(int i=0;i<2;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(book[xx][yy]||(xx%2==0&&yy%2==0))continue;
        if(xx<1||yy<1||xx>n||yy>m)continue;
        book[xx][yy]=true;
        dfs(xx,yy);
        book[xx][yy]=false;
    }
}
int main()
{
    cin>>n>>m;
    dfs(1,1);
    cout<<ans;
    return 0;
}

22 评论

CHENL 2022-04-06 23:32

这道题dfs复杂度是多少呢

泡椒_ 10个月前

指数

细雨 2022-03-13 10:46

为什么单独设定dp[1][1]=1啊？

云夜 2022-03-17 21:01

请问大佬，为什么要写成f[i][j]+=f[i-1][j]+f[i][j-1];而不是f[i][j]=f[i-1][j]+f[i][j-1];呢

玛卡玛卡 2022-03-22 22:25

我也想知道为什么麻烦你知道答案了和我说一声

Lay水水 2022-03-27 09:38 回复了玛卡玛卡的评论

这样写你应该就能看懂了

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;


public class acwing2067走方格 {

    static int n,m;
    static int dp[][]  = new int[35][35];

    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= m ; j++) {
                if (i==1 && j==1){
                    dp[i][j]=1;
                    continue;
                }
                if (i%2!=0 ||j%2!=0)
                    dp[i][j]  =  dp[i-1][j]+dp[i][j-1];
                System.out.println(i+" "+j+" "+dp[i][j]);
            }
        }
        System.out.println(dp[n][m]);
    }





}

云夜 2022-04-06 21:21 回复了 Lay水水的评论

这个能过吗？

云夜 2022-04-06 21:24 回复了玛卡玛卡的评论

请问兄弟他的代码你理解吗，我还是不理解

Lay水水 2022-04-06 22:45 回复了云夜的评论

能过，我的是java的，你c++对应改下跟我一样的逻辑就行

Turbo_90 2022-12-12 12:03 回复了玛卡玛卡的评论

因为刚开始循坏到i=1,j=1的时候如果不这样写 a[1][1]就会变成0，刚开始矩阵默认为0，加上0不受影响，或者你可以在循环里面加判断语句 if(i==1 && j==1 ) continue;

生活明朗万物可爱 9个月前回复了 Lay水水的评论

非常感谢，看懂了

追逐光成为光 2022-02-03 22:57

大佬你好，请问为什么“假如当前行列都不为偶数” 而代码里面“if(i%2!=0||j%2!=0)”用的是||不是&&?

宇宙_5 2022-02-05 12:40

都不是偶数才行有一个是偶数满足题意

追逐光成为光 2022-02-05 15:09 回复了宇宙_5 的评论

噢噢我明白了，谢谢！

与星星私奔 2022-01-15 22:19

dp[i]为什么要+=啊

宇宙_5 2022-02-05 16:23

有的dp[i]初始值不是0,需要加原来的

匆匆_9 2021-04-16 19:45

void dfs(int x,int y)
{
if(x==n&&y==m)
{
count++;
sum=count;
return;
}

for(i=0;i<2;i++)
{
    int tx,ty;
    tx=x+dx[i];
    ty=y+dy[i];


    if(tx<1||ty<1||tx>n||ty>m) continue;
    if(v[tx][ty]==true) continue;


    v[tx][ty]=true;
    dfs(tx,ty);
    v[tx][ty]=false;

}
return;

}
请问我这个函数哪里写错了… 我去掉了判断奇偶数的条件但是输出一下遍历的位置只有一条路径