题解 | #走方格的方案数#
走方格的方案数
http://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b
题意
沿n 乘 m的棋盘边界从左上角,只能向右或向下走到右下角的方案数
限制:n和m均不超过8
方法
递推
既然只能向右或者向下走,反过来说明一个位置要么从上方来,要么从左方来。切因为上一个点不同,所以这两个方向来的各不相同
定义 表示从左上角走到第行,第列的方案数
那么它上方的格子的方案数为,它左方的格子的方案数为
有递推表达式 ,
因为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;
}
复杂度分析
时间复杂度: 因为计算了所有答案,所以时间复杂度为
空间复杂度: 因为记录了所有答案所以空间复杂度为
递归+记忆化
注意到上面预处理了所有结果,但实际上可能要询问的并没有这么多
所以可以直接把转化为递归关系,其中任意一侧为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;
}
复杂度分析
时间复杂度: 最坏情况所有格子被计算一次,
空间复杂度: 最坏情况会记忆所有格子,