方格走法
方格走法
http://www.nowcoder.com/questionTerminal/56f412b9e17e4504b1bbeca96f94a263
题目难度：一星
考察点：动态规划
方法：动态规划
1.分析：
这个题我们采用动态规划的算法，设dp[i][j]表示位于坐标(i,j)时所有的走法数目，那么我们可以想坐标(i,j)可以由什么地方走到，那么显然由于小团只能向右或向下走，所以(i,j)只能由(i, j-1)和(i-1,j)坐标走到，所以就有如下状态转移方程：
初始化所有的dp[0][i] = dp[i][0] = 1。
初始化所有的dp[0][i] = dp[i][0] = 1。
拿样例来说：
算法实现：
(1). 输入一个n, m。 (2). 初始化所有的dp[0][i] = dp[i][0] = 1。
(3). 按照上状态转移方程进行求解dp[i][j]。
(4). 输出dp[n][m]
2.复杂度分析：
时间复杂度：O(n*m)空间复杂度：O(n*m)
3.代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e2+5;
int dp[MAXN][MAXN];
int main(){
int n, m; cin>>n>>m;
for(int i=0; i<MAXN; i++) dp[0][i] = dp[i][0] = 1;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) dp[i][j] = dp[i-1][j] + dp[i][j-1];
cout<<dp[n][m]<<endl;
return 0;
} 
字节跳动公司氛围 560人发布
