牛客题霸-简单变向-动态规划解
牛客题霸-简单变向
牛牛准备在一个3行n列的跑道上跑步。一开始牛牛位于(1,1)。
当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：
- 跑到第i行第j+1列
- 跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
- 跑到第i+1行第j+1列（如果i=3则不可以这么跑）。
跑道上有一些格子设置了路障(一个格子可能有多个路障)，牛牛不能跑到路障上。现在牛牛想知道，从(1,1)到(3,n)有多少条不同的路径？
为了防止答案过大，答案对1e9+7取模。
输入
4,1,[1],[2]
输出
2
说明
在第一行第二列的位置有一个障碍
牛牛有两种跑法：
- (1,1)->(2,2)->(2,3)->(3,4)
- (1,1)->(2,2)->(3,3)->(3,4)
解
| 1 | # | 1 | 2 |
|---|---|---|---|
| 0 | 1 | 1 | 3 |
| 0 | 0 | 1 | 2 |
如上表所示，(1, 1)是起点，(1, 2)是路障，要到达(2, 2)只能从(1, 1)、(2, 1)，因此到达2行2列的路径有 0 + 1 = 1 条。
同理，
(1, 3) = (1, 2) + (2, 2) = 0 + 1 = 1
(2, 3) = (1, 2) + (2, 2) + (3, 2) = 0 + 1 + 0 = 1
(3, 3) = (2, 2) + (3, 2) = 1 + 0 = 1
(1, 4) = (1, 3) + (2, 3) = 1 + 1 = 2
(2, 4) = (1, 3) + (2, 3) + (3, 3) = 1 + 1 + 1 = 3
(3, 4) = (2, 3) + (3, 3) = 1 + 1 = 2
因此到达(3, 4)的路径有2条。
const int mod = 1e9+7;
class Solution {
public:int solve(int n, int m, vector<int>& x, vector<int>& y) {// write code herevector<vector<long long> > dp(4);dp[1].resize(n+1);dp[2].resize(n+1);dp[3].resize(n+1);//设置路障for(int i = 0; i < m; i++)dp[x[i]][y[i]] = -1;//第一列的初始值dp[1][1] = 1;dp[2][1] = 0;dp[3][1] = 0;for(int i = 2; i <= n; i++){//路障上的路径数为 0dp[1][i] = dp[1][i] == -1 ? 0 : (dp[1][i-1] + dp[2][i-1]) % mod;dp[2][i] = dp[2][i] == -1 ? 0 : (dp[1][i-1] + dp[2][i-1] + dp[3][i-1]) % mod;dp[3][i] = dp[3][i] == -1 ? 0 : (dp[2][i-1] + dp[3][i-1]) % mod;}return dp[3][n];}
};
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！