题目描述
给定一个n*m的方格阵,沿着方格的边线走,从左上角(0,0)开始,每次只能往右或者往下走一个单位距离,问走到右下角(n,m)一共有多少种不同的走法。
输入格式
共一行,包含两个整数n和m。
输出格式
共一行,包含一个整数,表示走法数量。
数据范围
1≤n,m≤10
样例
输入样例:
2 3
输出样例:
10
算法1
(动态规划)
大概就是说从左上角走到右下角的终点,每次只能向右或者向下走一步,求所有可能的唯一路径共有多少条。最容易想到的应该就是用DFS或者BFS将所有可能的解进行枚举。就是这么暴力!!!
但是时间复杂度 应该过不了!!!
使用动态规划的话
走到终点的所有路径和 = 走到1位置的所有路径和 + 走到2位置的所有路径和
也就是DP状态转移方程
dp[3] = dp[1]+dp[2];
leetcode 有道几乎一模一样的题目,就是本题的边界相对有点怪
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<vector<int>> v(12,vector<int>(12,0));
int main()
{
cin >> n >>m;
vector<vector<int>> vv(m +2, vector<int>(n + 2, 0));
vv[1][1] = 0;
vv[1][2] = 1;
vv[2][1] = 1;
for (int i = 1; i <= m+1; i++) {
for (int j = 1; j <= n+1; j++) {
vv[i][j] = std::max(vv[i - 1][j] + vv[i][j - 1], vv[i][j]);
}
}
cout << vv[m+1][n+1];
return 0;
}