数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中在若干步后停留在同一位置的方法数
假设有一个大小为 arrLen 的数组，并且我们在该数组的索引 0 处有一个指针。在每一步中，我们可以在数组中向左移动 1 个位置，向右移动 1 个位置，或者停留在同一位置。
现在假设我们有两个整数 steps 和 arrLen，我们必须找到指针在恰好 steps 步后仍然位于索引 0 的方法数。如果答案非常大，则将其返回模 10^9 + 7。
因此，如果输入类似于 steps = 3，arrLen = 2，则输出将为 4，因为有 4 种不同的方法可以在 3 步后停留在索引 0。这些是 [右，左，停留在原处]，[停留在原处，右，左]，[右，停留在原处，左]，[停留在原处，停留在原处，停留在原处]。
为了解决这个问题，我们将遵循以下步骤 -
m := 1e9 + 7
定义一个函数 add()，它将接收 a、b，
返回 (a mod m + b mod m) mod m
定义一个二维数组 dp
定义一个函数 solve()，它将接收 n、x、pos 并将其初始化为 0，
如果 x 等于 0，则 -
当 pos 等于 0 时返回 true
如果 dp[pos, n] 不等于 -1，则 -
返回 dp[pos, n]
ans := 0
如果 pos > 0，则
ans := add(ans, solve(n, x - 1, pos - 1))
如果 pos < n - 1，则 -
ans := add(ans, solve(n, x - 1, pos + 1))
ans := add(ans, solve(n, x - 1, pos))
dp[pos, n] := ans
返回 ans
从主方法执行以下操作 -
x := arrLen 和 steps / 2 + 1 的最小值
dp := 定义一个大小为 2 x (x + 1) 的二维数组，用 0 填充它
dp[0, 0] := 1
n := arrLen
对于初始化 i := 1，当 i <= steps 时，更新（i 增加 1），执行 -
对于初始化 j := 0，当 j < arrLen 和 step/2 + 1 的最小值时，更新（j 增加 1），执行 -
x := (i - 1) mod 2
y := i mod 2
dp[y, j] := dp[x, j]
如果 j - 1 >= 0，则 -
dp[y, j] := add(dp[y, j], dp[x, j - 1])
如果 j + 1 < n，则 -
dp[y, j] := add(dp[y, j], dp[x, j + 1])
返回 dp[steps mod 2, 0]
让我们看看以下实现以获得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
lli add(lli a, lli b){
return (a % MOD + b % MOD) % MOD;
}
class Solution {
public:
vector<vector<int> > dp;
int solve(int n, int x, int pos = 0){
if (x == 0) {
return pos == 0;
}
if (dp[pos][n] != -1)
return dp[pos][n];
int ans = 0;
if (pos > 0)
ans = add(ans, solve(n, x - 1, pos - 1));
if (pos < n - 1)
ans = add(ans, solve(n, x - 1, pos + 1));
ans = add(ans, solve(n, x - 1, pos));
dp[pos][n] = ans;
return ans;
}
int numWays(int steps, int arrLen){
int x = min(arrLen, steps / 2 + 1);
this->dp = vector<vector<int> >(2, vector<int>(x + 1, 0));
dp[0][0] = 1;
int n = arrLen;
for (int i = 1; i <= steps; i++) {
for (int j = 0; j < min(arrLen, steps / 2 + 1); j++) {
int x = (i - 1) % 2;
int y = i % 2;
dp[y][j] = dp[x][j];
if (j - 1 >= 0)
dp[y][j] = add(dp[y][j], dp[x][j - 1]);
if (j + 1 < n)
dp[y][j] = add(dp[y][j], dp[x][j + 1]);
}
}
return dp[steps % 2][0];
}
};
main(){
Solution ob;
cout << (ob.numWays(3,2));
}输入
3, 2
输出
4
208 次查看
