题目描述

数据范围
1≤n,m≤30 估摸着是指数级别，没怎么分析时间复杂度，直接上手写dfs了。

dfs

走格子问题我习惯用dfs，简单容易写

C++ 代码

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

DP

动态规划

提交后，十个样例过了九个，dfs过不了转换思路为dp。怎么从dfs转换成dp呢？
dp两个点要特别注意，一个是状态转移方程，一个是初始化条件。 状态转移方程显而易见
若【i】【j】合法，st[i][j] = st[i-1][j] + st[i][j -1]
初始化也很简单，m = 1 ，或 n = 1 时，st = 1；

对比dfs的思路 判断i j 是否合法，在dfs也需要判定。状态转移方程想出来后，敲代码十分简单

时间复杂度

这个比较好分析 m*n

C++ 代码

#include <iostream>
#include <algorithm>
#include<cstdio>
#include <cstring>
 using namespace std;
 int m,n,st[32][32];

 int main(){
    cin>>n>>m;
    for(int i = 0 ; i < 32 ; i ++){
        st[i][1] = 1 ;
        st[1][i] = 1 ;
    }
    for(int i = 2 ; i <= n ; i ++){
        for(int j = 2 ; j<= m ; j++){
            if( i%2 + j %2 == 0){
                st[i][j] = 0;
            }
            else {
                st[i][j] = st[i-1][j] + st[i][j -1];
            }

        }
    }
    //dfs(1,1);
    cout<<st[n][m];
    return 0;
 }