题解 | #走方格的方案数#

走方格的方案数

http://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b

题意

沿n 乘 m的棋盘边界从左上角,只能向右或向下走到右下角的方案数

限制:n和m均不超过8

方法

递推

既然只能向右或者向下走,反过来说明一个位置要么从上方来,要么从左方来。切因为上一个点不同,所以这两个方向来的各不相同

定义dp[i][j]dp[i][j] 表示从左上角走到第ii行,第jj列的方案数

那么它上方的格子的方案数为dp[i1][j]dp[i-1][j],它左方的格子的方案数为dp[i][j1]dp[i][j-1]

有递推表达式 dp[i][j]=dp[i1][j]+dp[i][j1]dp[i][j] = dp[i-1][j] + dp[i][j-1]

因为n和m比较小,可以提前计算所有答案,每次询问时直接输出答案

- 0 1 2 3 4 5 6 7 8
0 1 1 1 1 1 1 1 1 1
1 1 2 3 4 5 6 7 8 9
2 1 3 6 10 15 21 28 36 45
3 1 4 10 20 35 56 84 120 165
4 1 5 15 35 70 126 210 330 495
5 1 6 21 56 126 252 462 792 1287
6 1 7 28 84 210 462 924 1716 3003
7 1 8 36 120 330 792 1716 3432 6435
8 1 9 45 165 495 1287 3003 6435 12870

从直观上看,就是递推时,一个格子的值等于它上方和它左方的值的和

代码

#include<bits/stdc++.h>
using namespace std;

int dp[10][10];

int main(){
    int n,m;
    dp[0][1] = 1; // 保证dp[1][1] 为 1
    for(int i = 1;i < 10;i++){
        for(int j = 1;j < 10;j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 递推式
        }
    }
    while(~scanf("%d %d",&n,&m)){
        printf("%d\n",dp[n+1][m+1]); // 直接输出答案
    }
    
    return 0;
}

复杂度分析

时间复杂度: 因为计算了所有答案,所以时间复杂度为O(mn)O(mn)

空间复杂度: 因为记录了所有答案所以空间复杂度为O(mn)O(mn)

递归+记忆化

注意到上面预处理了所有结果,但实际上可能要询问的并没有这么多

所以可以直接把dp[i][j]=dp[i1][j]+dp[i][j1]dp[i][j] = dp[i-1][j] + dp[i][j-1]转化为递归关系,其中任意一侧为0时达到了边界返回1

这样的话,有些结果会被重复计算,于是加上记忆化让每个格子最多被算一次

代码

#include<bits/stdc++.h>
using namespace std;

int dp[10][10];

int dfs(int i,int j){
    if(i == 0 || j == 0)return 1; // 边界
    if(dp[i][j])return dp[i][j]; // 记忆化
    return dp[i][j] = dfs(i-1,j)+dfs(i,j-1); // 储存结果
}

int main(){
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        printf("%d\n",dfs(n,m)); // 调用递归
    }
    return 0;
}

复杂度分析

时间复杂度: 最坏情况所有格子被计算一次,O(nm)O(nm)

空间复杂度: 最坏情况会记忆所有格子,O(mn)O(mn)

全部评论

相关推荐

jack_miller:我给我们导员说我不在这里转正,可能没三方签了。导员说没事学校催的时候帮我想办法应付一下
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务