[编程题]机器人达到指定位置方法数
- 热度指数：7876 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种。由于方案数可能比较大，所以答案需要对1e9+7取模。
输入描述:
输出包括一行四个正整数N（2<=N<=5000）、M(1<=M<=N)、K(1<=K<=5000)、P(1<=P<=N)。
输出描述:
输出一个整数，代表最终走到P的方法数对取模后的值。
示例1
输入
5 2 3 3
输出
3
说明
1).2->1,1->2,2->3
2).2->3,3->2,2->3
3).2->3,3->4,4->3
示例2
输入
1000 1 1000 1
输出
591137401
说明
注意答案要取模
备注:
时间复杂度,空间复杂度
。
#include<iostream>
#include<vector>
using namespace std;
int main() {
int N, M, K, P;
int mod = 1e9 + 7;
cin >> N >> M >> K >> P;
vector<int> list;
list.push_back(0);
for (int i = 1; i <= N; i++) list.push_back(i);
list.push_back(0);
vector<int> last(N + 2, 0);
last[M] = 1;
vector<int> cur(N + 2, 0);
for (int step = 0; step < K; step++) {
for (int i = 1; i <= N; i++) {
cur[i] = (last[i - 1] + last[i + 1])%mod;
}
for (int i = 1; i <= N; i++) last[i] = cur[i];
}
cout << cur[P] << endl;
} 使用两个vector来模拟dp表中当前的列和上一列
然后状态转移方程为：
当前步数=左边可能情况+右边可能情况
之后就可以根据给出的步数限制，从初始位置开始计算到其他位置可能的情况了。
为了统一结果在数组开头和结尾添加一个0，这样就不需要判断是否为对首还是队尾了。
编辑于 2019-09-30 02:35:43
回复(2)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main(){
int n,m,k,p;
cin>>n>>m>>k>>p;
int dp[n+1], a[n+1];
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
a[m] = 1;
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
if(j==1)
dp[j] = a[j+1];
else if(j==n)
dp[j] = a[j-1];
else
dp[j] = (a[j-1]+a[j+1])%MOD;
}
for(int j=0;j<=n;j++)
a[j] = dp[j];
}
cout<<dp[p]<<endl;
return 0;
}
发表于 2020-02-11 08:44:29
回复(1)
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int inf=1000000007;
int dp[5010][5010]={0};
int main(){
int N,M,K,P;
scanf("%d %d %d %d",&N,&M,&K,&P);
for(int i=1;i<=N;++i){
if(abs(i-M)==1){
dp[1][i]=1;
}
}
for(int j=2;j<=K;++j){
for(int i=1;i<=N;++i){
if(i==1)
dp[j][i]=dp[j-1][i+1];
else if(i==N)
dp[j][i]=dp[j-1][i-1];
else
dp[j][i]=(dp[j-1][i-1]+dp[j-1][i+1])%inf;
}
}
printf("%d\n",dp[K][P]);
}
编辑于 2020-04-21 21:22:15
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int mod = 1e9+7;
/*
暴力递归->动态规划->空间压缩
解析：当前处于cur位置，还剩rest步要走；1<=cur<=N
1. cur==1,那么下一步只能往右走，也就是走到2，还剩rest-1步；
2. cur==N,那么下一步只能往左走，也就是走到N-1，还剩rest-1步；
3. cur在中间位置，可以往左(cur-1)或者右走(cur+1),还剩rest-1步，
4.终止条件：rest==0,若定在p处，返回1表示能走到，返回0表示未走到；
*/
int walk1(int N, int cur, int rest, int P)
// N:一共N个位置
// cur:当前所处位置
// rest:还剩多少步
// p:目标地点
{
if(rest == 0) return cur==P ? 1: 0;
if(cur == 1)
return walk1(N, 2, rest-1, P);
if(cur == N)
return walk1(N, N-1, rest-1, P);
return walk1(N, cur-1, rest-1, P) + walk1(N, cur+1, rest-1, P);
}
int walk2(int N, int cur, int rest, int P)
/*
考虑dp分析：
1.确定算法无后效性，也就是当前状态到终止状态，与过去状态到达当前状态无关；
2.对可变参数建立table，记录base case；根据base case计算其他未知格子；
3.返回目标格子记录的值；
*/
{
//1.可变参数为cur,cur的范围在N内，还有参数rest;
vector<vector<int>> dp(rest+1,vector<int>(N+1, 0));
//当rest为0,那么直接返回0,1（目标位置P）；
dp[0][P] = 1;
//可以推测walk1,中其他的三个情况下，每一个行（rest）,都仅仅依赖于上一行的结果（rest-1）,因此有了第一行结果，便可
//求解全部的结果
for(int row=1; row<=rest; ++row)//row表步数rest,col表当前位置cur
for(int col=1; col<=N; ++col)
{
if(col==1)
dp[row][col] = dp[row-1][2] %mod; //easy error: set 2
else if(col==N)
dp[row][col] = dp[row-1][N-1] %mod; //easy error: set 2N-1
else
dp[row][col] = (dp[row-1][col-1] + dp[row-1][col+1])%mod;
}
return dp[rest][cur]%mod; //返回目标步数为rest，终点为P的结果
}
int walk3(int N, int cur, int rest, int P)
/*
dp:每次递增rest，每个位置记录是否满足要求步数抵达的值；
*/
{
//rest为0的dp状态
vector<int> dp(N+1, 0);
dp[P] = 1;
for(int i=1; i<=rest; ++i) //一直更新到指定步数
{
int leftUp = dp[1];
for(int j=1; j<=N; ++j)
{
int tmp = dp[j];
if(j==1){
dp[j] = dp[2] % mod; //dp[j+1]恰好是上一行右以为的结果，即rest-1,在2位置。
}else if(j==N){
dp[j] = leftUp % mod; //leftUp恰好是上一行左边的结果，即rest-1,在n-1位置。
}else{
dp[j] = (leftUp+dp[j+1]) % mod;
}
leftUp=tmp;
}
}
return dp[cur] % mod; //从cur开始走rest步的答案
}
int main(){
int N, M, K, P;
cin >> N >> M >> K >> P;
if(N<2 || K<1 || M>N || M<1|| P>N || P<1)
return 0;
cout << walk3(N, M, K, P) << endl;
return 0;
}
发表于 2019-08-23 08:07:26
回复(1)
我们先可以分析这个过程，记机器人当前的位置为cur，终点位置为end，还剩下能走的步数为rest。则针对机器人此时所在的不同位置，有如下的三种情况：
- 机器人在左边界1，那它下一步只能往右走；
- 机器人在右边界n，那它下一步只能往左走；
- 机器人在中间位置1<i<n，它下一步可以往左也可以往右。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]);
int s = Integer.parseInt(params[1]);
int k = Integer.parseInt(params[2]);
int e = Integer.parseInt(params[3]);
System.out.println(recurrent(n, s, k, e));
}
private static int recurrent(int n, int cur, int rest, int end) {
if(rest == 0){
// 没有步数了，如果到达了目的地，就生成了一种走法，否则走法无效
return cur == end? 1: 0;
}else if(cur == 1){
// 到达左边界，只能往右走，步数减1
return recurrent(n, cur + 1, rest - 1, end, memory) % 1000000007;
}else if(cur == n){
// 到达右边界，只能往左走，步数减1
return recurrent(n, cur - 1, rest - 1, end, memory) % 1000000007;
}else{
// 中间位置可以往两边走
return (recurrent(n, cur - 1, rest - 1, end, memory) + recurrent(n, cur + 1, rest - 1, end, memory)) % 1000000007;
}
}
} 这种递归的做法逻辑还是很清晰的，可以大体上视为每一步都有两种选择，一共有k步，时间复杂度就是2k指数级别，当k很大时会产生指数爆炸，从而超时。假设递归函数为f，仅传入两个变化的参数cur和rest（n，start和end是固定的，这里省略），假设n=5，start=2，k=4，我们要求的是f(2,,4)，就会得到如下图的展开： 
可以很明显的发现，f(2,2)在左右两个子树都用到了，但每次碰到它都需要展开计算。也就是说，暴力递归存在很多重复计算。对于这种情况，我们可以采用记忆化搜索来进行剪枝，每次返回的时候将结果填入表中，如果第二次再碰到相同的情况就直接返回，无需再往下递归计算。考虑到cur的范围是1~n，rest的范围是0~k，因此记忆化搜索表可以开个(k+1)*(n+1)大小的二维数组，得到如下的记忆化搜索版本：
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]);
int s = Integer.parseInt(params[1]);
int k = Integer.parseInt(params[2]);
int e = Integer.parseInt(params[3]);
// 初始状态改为无意义的-1
int[][] memory = new int[k + 1][n + 1];
for(int i = 0; i <= k; i++){
for(int j = 0; j <= n; j++)
memory[i][j] = -1;
}
System.out.println(recurrent(n, s, k, e, memory));
}
private static int recurrent(int n, int cur, int rest, int end, int[][] memory) {
// 有记忆，直接返回
if(memory[rest][cur] != -1) return memory[rest][cur];
if(rest == 0){
// 没有步数了，如果到达了目的地，就生成了一种走法，否则走法无效
memory[rest][cur] = cur == end? 1: 0;
}else if(cur == 1){
// 到达左边界，只能往右走，步数减1
memory[rest][cur] = recurrent(n, cur + 1, rest - 1, end, memory) % 1000000007;
}else if(cur == n){
// 到达右边界，只能往左走，步数减1
memory[rest][cur] = recurrent(n, cur - 1, rest - 1, end, memory) % 1000000007;
}else{
// 中间位置可以往两边走
memory[rest][cur] = (recurrent(n, cur - 1, rest - 1, end, memory) + recurrent(n, cur + 1, rest - 1, end, memory)) % 1000000007;
}
return memory[rest][cur];
}
} 仍然是递归，但由于在递归函数的开头就判断了记忆表中是否有f(cur,rest)，所以这棵树被进行了大量的剪枝，其实只是不断在填表而已，表的大小是(k+1)*(n+1)，因此时间复杂度为O(k*n)，以O(k*n)的空间节省了递归展开的时间。 而动态规划其实就是这个记忆化搜索的填表过程，我们根据递归中的依赖关系可以写出动态规划的版本。对于某个位置dp[cur][rest]，有如下三种情况：
- 当cur=1时，它依赖的是右上角的位置，因此状态转移方程为：
- 当cur=n时，它依赖的是左上角的位置，因此状态转移方程为：
- 当1<cur<n时，它依赖的是左右上角之和，因此状态转移方程为：
import scala.io.StdIn
object Main {
def main(args: Array[String]): Unit = {
val in = StdIn
val params = in.readLine().split(" ")
val n = params(0).toInt
val start = params(1).toInt
val k = params(2).toInt
val end = params(3).toInt
val dp = Array.ofDim[Int](k + 1, n + 1)
dp(0)(end) = 1 // 剩下0步，到达了end，根据递归函数，直接出来一种方案
// 填表，注意第一列是废的
for(rest <- 1 to k; cur <- 1 to n){
if(cur == 1)
dp(rest)(cur) = dp(rest - 1)(cur + 1) % 1000000007
else if(cur == n)
dp(rest)(cur) = dp(rest - 1)(cur - 1) % 1000000007
else
dp(rest)(cur) = (dp(rest - 1)(cur - 1) + dp(rest - 1)(cur + 1)) % 1000000007
}
println(dp(k)(start))
}
}
编辑于 2021-11-20 10:33:20
回复(0)
import java.util.*;
public class Main {
public static int mod = (int)1e9+7;
public static void main(String[] args) {
Scanner scann = new Scanner(System.in);
int N = scann.nextInt();
int M = scann.nextInt();
int K = scann.nextInt();
int P = scann.nextInt();
System.out.println(walk(N, M, K, P));
}
public static int walk(int N, int M, int K, int P) {
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
int[][] dp = new int[K + 1][N + 1];
dp[0][P] = 1;
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= N; j++) {
if (j == 1) {
dp[i][j] = dp[i - 1][2] % mod;
} else if (j == N) {
dp[i][j] = dp[i - 1][N - 1] % mod;
} else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
}
}
}
return dp[K][M] % mod;
}
}
发表于 2019-10-04 11:15:09
回复(1)
机器人达到指定位置方法数
假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种。由于方案数可能比较大，所以答案需要对10^9^+7取模。
输入描述:
输出包括一行四个正整数N（2<=N<=5000）、M(1<=M<=N)、K(1<=K<=5000)、P(1<=P<=N)。
输出描述:
输出一个整数，代表最终走到P的方法数对10^9^+7取模后的值。
输入样例1
5 2 3 3
输出样例1
3
说明
1).2->1,1->2,2->3 2).2->3,3->2,2->3 3).2->3,3->4,4->3
输入样例2
1000 1 1000 1
输出样例2
591137401
说明
注意答案要取模
题解1
// 暴力
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 10;
int n,m,k,p;
int DFS(int u,int resi)
{
if(resi == 0) return u == p ? 1 : 0;
int ans = 0;
if(u != n) ans = DFS(u + 1,resi - 1) % MOD;
if(u != 1) ans += DFS(u - 1,resi - 1) % MOD;
return ans % MOD;
}
int main(void)
{
cin >> n >> m >> k >> p;
cout << DFS(m,k);
return 0;
} 题解2
// 计划性搜索
// 复杂度O(N*K),总有一刻表里填满数据,之后就全是O(1)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010,MOD = 1e9 + 7;
int f[N][N];
int n,m,k,p;
int DFS(int u,int resi)
{
if(f[u][resi] != -1) return f[u][resi];
if(resi == 0)
{
f[u][resi] = (u == p) ? 1 : 0;
return f[u][resi];
}
int ans = 0;
if(u != n) ans = DFS(u + 1,resi - 1) % MOD;
if(u != 1) ans += DFS(u - 1,resi - 1) % MOD;
f[u][resi] = ans % MOD;
return f[u][resi];
}
int main(void)
{
cin >> n >> m >> k >> p;
memset(f,-1,sizeof f);
cout << DFS(m,k);
return 0;
} 题解3
// DP
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010,MOD = 1e9 + 7;
int f[N][N];
int n,m,k,p;
int main(void)
{
cin >> n >> m >> k >> p;
f[m][0] = 1; // row: n, column: k
for(int j = 1; j <= k; j++)
for(int i = 1; i <= n; i++)
f[i][j] = (f[i + 1][j - 1] % MOD + f[i - 1][j - 1] % MOD) % MOD;
cout << f[p][k] << endl;
return 0;
} 题解4
// DP + 状态压缩(滚动数组)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010,MOD = 1e9 + 7;
int f[N],backup[N];
int n,m,k,p;
int main(void)
{
cin >> n >> m >> k >> p;
f[m] = 1;
for(int j = 1; j <= k; j++)
{
memcpy(backup,f,sizeof backup);
for(int i = 1; i <= n; i++)
f[i] = (backup[i + 1] % MOD + backup[i - 1] % MOD) % MOD;
}
cout << f[p] << endl;
return 0;
}
发表于 2022-09-12 15:40:29
回复(0)
参考大佬的代码，加了注释
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7; // 取模数
int main()
{
int n, m, k, p;
cin >> n >> m >> k >> p;
// 定义 dp[i][j] 表示在只能走 i 步的情况下，到达位置 j 的方案数
vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
// 初始化在只能走 1 步的情况下，到达起点 m 的方案数为 1
for(int i = 1; i <= n; ++i){
if(abs(i - m) == 1){
dp[1][i] = 1;
}
}
for(int i = 2; i <= k; ++i){ // 遍历步数
for(int j = 1; j <= n; ++j){ // 遍历位置
// 在1位置，那么下一步机器人只能走到2位置，即往前一步 j+1，同时消耗步数 i-1
if(j == 1) dp[i][j] = dp[i - 1][j + 1];
// 在N位置，那么下一步机器人只能走到N-1位置，即往回一步 j-1，同时消耗步数 i-1
else if(j == n) dp[i][j] = dp[i - 1][j - 1];
//其他情况，可往左或者往右走，即可 j+1 和 j-1，但是都得消耗步数 i-1，同时要取模
else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
}
}
cout << dp[k][p]; // 返回走 k 步情况下，到达终点 p 的方案数
return 0;
}
发表于 2022-04-07 17:03:34
回复(0)
C++,几乎双百分之百！
当前步数的情况=上一步中左边的情况+上一步中右边的情况
#include<iostream>
#include<vector>
using namespace std;
int main() {
int N, M, K, P;
int mod=1000000007;
cin>>N>>M>>K>>P;
vector<int> pre(N+2,0);
pre[M]=1;
vector<int> res(N+2,0);
for(int i=0;i<K;++i){
for(int j=1;j<=N;++j){
res[j]=(pre[j-1]+pre[j+1])%mod;
//当前步数的情况=上一步中左边的情况+上一步中右边的情况 }
pre=res;
}
cout<<pre[P];
}
发表于 2021-07-16 14:54:37
回复(0)
#include <iostream>
#include <vector>
using namespace std;
const static int mod = 1e9 + 7;
int process(int N, int P, int cur, int rest, vector<vector<int>>& v){
if(v[cur][rest] != -1)
return v[cur][rest];
if(rest == 0){
v[cur][rest]= cur == P ? 1 : 0;
return v[cur][rest];
}
//res > 0
if(cur == 1){
v[cur][rest] = process(N, P, 2, rest - 1, v) % mod;
return v[cur][rest];
}
if(cur == N){
v[cur][rest] = process(N, P, N - 1, rest - 1, v) % mod;
return v[cur][rest];
}
//中间位置
v[cur][rest] = (process(N, P, cur + 1, rest - 1, v) % mod
+ process(N, P, cur - 1, rest - 1, v) % mod) % mod;
return v[cur][rest];
}
int MemorySearch(int N, int P, int M, int K){
//N + 1行 K + 1列
vector<vector<int>> v(N + 1, vector<int>(K + 1, -1));
return process(N, P, M, K, v);
}
int main(void){
int N, M, K, P;
cin >> N >> M >> K >> P;
cout << MemorySearch(N, P, M, K) << endl;
return 0;
}
在笔试的时候，不应该用动态规划写，而应该尽量用记忆化搜索来写，又快有方便。
这里遇到一个问题
就是mod相关问题
需要注意的代码是
v[cur][rest] = (process(N, P, cur + 1, rest - 1, v) % mod
+ process(N, P, cur - 1, rest - 1, v) % mod) % mod;
出了分开mod，还需要合起来mod
v[cur][rest] = (process(N, P, cur + 1, rest - 1, v) % mod
+ process(N, P, cur - 1, rest - 1, v) % mod) % mod;
出了分开mod，还需要合起来mod
动态规划解法：
#include <iostream>
#include <vector>
using namespace std;
const static int mod = 1e9 + 7;
int dp(int N, int K, int M, int P){
vector<vector<int>> dpArr(N + 1, vector<int>(K + 1));
dpArr[P][0] = 1;
for(int j = 1; j <= K; j++){
for(int i = 1; i <= N; i++){
if(i == 1)
dpArr[i][j] = dpArr[2][j - 1];
else if(i == N)
dpArr[i][j] = dpArr[N - 1][j - 1];
else
dpArr[i][j] = (dpArr[i + 1][j - 1] % mod + dpArr[i - 1][j - 1] % mod) % mod;
}
}
return dpArr[M][K];
}
int main(void){
int N, M, K, P;
cin >> N >> M >> K >> P;
cout << dp(N, K, M, P) << endl;
return 0;
} 错误原因主要在于if else是否未写对 以后遇到段错误，一定是数组出现错误，一定要检查是否其他原因导致数组越界。
#include <iostream>
#include <vector>
using namespace std;
const static int mod = 1e9 + 7;
int dpProcess(int N, int K, int M, int P){
vector<vector<int>> v(K + 1, vector<int>(N + 1, 0));
v[0][P] = 1;
for(int i = 1; i <= K; i++){
for(int j = 1; j <= N; j++){
if(j == 1){
v[i][j] = v[i - 1][j + 1];
}
else if(j == N){
v[i][j] = v[i - 1][j - 1];
}
else{
v[i][j] = (v[i - 1][j - 1] % mod + v[i - 1][j + 1] % mod) % mod;
}
}
}
return v[K][M];
}
int main(void){
int N, M, K, P;
cin >> N >> M >> K >> P;
cout << dpProcess(N, K, M, P) << endl;
return 0;
} 动态规划一定要注意行为个数比较好些。
编辑于 2021-06-01 15:53:41
回复(0)
#include<iostream>
#include<cstring>
using namespace std;
const int N = 5010, mod = 1e9+7;
long long f[N], g[N];
int main(){
int n, m, k, p;
cin>>n>>m>>k>>p;
f[m] = 1;
for(int i = 1;i<=k;i++){
memcpy(g, f, sizeof f);
for(int j = 1;j<=n;j++)
{
//cout<<f[j-1]<<" "<<f[j+1]<<endl;
f[j] = (g[j-1] + g[j+1])%mod;
}
}
cout<<f[p]<<endl;
return 0;
}
发表于 2021-05-18 14:46:04
回复(0)
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
int n, m, k, p;
int t = (int)(pow(10, 9) + 7);
while(cin >> n >> m >> k >> p){
vector<vector<int> > dp(k+1,vector<int>(n+1));
// dp[i][j]走i步到达j位置的方法数 = dp[i-1][j-1] + dp[i-1][j+1]
for(int i = 1; i <= k; i++){
for(int j = 1; j<= n; j++){
if(i == abs(m-j)) //步数等于始末间距时为1 小于时为0
dp[i][j] = 1;
else if(i > abs(m-j) && j == 1)
dp[i][j] = dp[i-1][j+1] % t;
else if(i > abs(m-j) && j == n)
dp[i][j] = dp[i-1][j-1] % t;
else if(i > abs(m-j))
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % t;
}
}
cout << dp[k][p] << endl;
}
return 0;
}
发表于 2021-04-09 12:31:05
回复(0)
import java.util.Scanner;
public class Main {
public static int mod = (int)1e9 + 7;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int P = sc.nextInt();
int[][] dp = new int[K + 1][N + 1];
dp[0][M] = 1;
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (j - 1 > 0) {
dp[i][j] += dp[i - 1][j - 1] % mod;
}
if (j + 1 <= N) {
dp[i][j] += dp[i - 1][j + 1] % mod;
}
}
}
System.out.println(dp[K][P] % mod);
}
}dp数组在每次相加的时候都需要进行mod运算
发表于 2021-04-07 17:14:01
回复(0)
const [ N, M, K, P ] = readline().split(' ').map(Number);
const mod = 10**9 + 7;
function dpCreator(rNum, cNum) {
const res = [];
for (let i = 0; i < rNum; i++) {
const row = [];
for (let j = 0; j < cNum; j++) {
row.push(0);
}
res.push(row);
}
return res;
}
function main(N, M, K, P) {
// 这是做过空间压缩后的dp表
// 在二维状态下是 dp[k][cur]，表示从位置 cur 开始走 k 步到达目标位置 P 的走法数。
// k 介于 [0...K]，前面添加一个 0 表示不走动时的情况；
// cur 介于 [0,1,...,N],前面添加一个 0 是为了统一计算，因为在计算 1 位置时，是不需要考虑往
// 左走动的情况的，但是处理从 2 开始的其他位置时，需要用到它左侧 dp[i - 1][j - 1] 的值，
// 所以在 1 位置左侧补充一位。
// 在空间压缩、按行滚动计算后，dp 表就成了一维的
const dp = new Array(N + 1).fill(0);
// 先初始化 dp 表第一行，表示 K === 0 时，即一步都不走时，到达目标位置 P 的走法数
// 显然只有当起始位置 M === P 时，才会一步都不用走就到目标位置，其他位置是不可能到达的
// 所以只有 dp[0][P] = 1，其他 dp[0][j] 都是 0，这也就是要在 [1...K] 之前再加一个 0
// 的方便之处
dp[P] = 1;
for (let i = 1; i <= K; i++) {
// 每当在更新新的一行的 dp[j] 位置的值，pre 变量保存的是上一行 dp[j - 1] 的值
// 在内层循环中，在每次将要更新旧的 dp[j] 之前，先用 tmp 变量保存当前行的旧 dp[j]
// 在 dp[j] 更新过程中，使用的 pre 其实还是上一行中的 dp[j - 1]，而当本轮 dp[j]
// 更新完成后，再把 tmp 中的该行旧 dp[j] 放到 pre 中，这样在接下来 j++ 后，pre 就
// 成了上一行的 dp[j - 1] 了
let pre = dp[0];
for (let j = 1; j <= N; j++) {
const tmp = dp[j];
if (j === 1) {
// 当处于最左侧的 1 位置时，要走到 P(P > 1) 位置，就只能往右走，也就是到 2
// 从 1 到 2 从走法上来说只有一种，而从位置 2 开始再到位置 P，其走法种数完全
// 取决于 dp[i - 1][2]，在空间压缩后，因为对于新滚到的一行是从左往右更新 dp[j]
// 当处理 dp[j] 时，dp[j + 1] 还是上一行的值，也就是 dp[i - 1][j + 1]，此时 j === 1
// 也就是 dp[i - 1][2]
// 在二维 dp 表中，相当于 dp[i][j] = dp[i - 1][j + 1]
dp[j] = dp[j + 1];
} else if (j === N) {
// 当处于最右侧的 N 位置时，要走到 P(P < N) 位置，就只能往左走，也就是到 N - 1
// 和位置 1 的情况类似，此时，dp[i][N] 也等同于 dp[i - 1][N - 1]
// 在二维 dp 表中，相当于 dp[i][j] = dp[i - 1][j - 1]
// 这里的 pre 就是前面说的动态不断保存 dp[i - 1][j - 1] 的值，此时就是 dp[i - 1][N - 1]
dp[j] = pre;
} else {
// 对于[2...N - 1]的位置而言，都有往左往右两种选择，所以 dp[i][j] 的值是左右两种走法数目之和
// 并注意，在这里就要对结果进行取模，防止数值巨大
// 在二维 dp 表中，相当于 dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j - 1]) % mod
dp[j] = (dp[j + 1] + pre) % mod;
}
pre = tmp;
}
}
// 在二维 dp 中相当于 dp[K][M]，表示从位置 M 走 K 步达到目标 P 的走法数
return dp[M];
}
console.log(main(N, M, K, P));
发表于 2021-02-16 22:43:01
回复(0)
只过25%。。。也不知道为啥，以及这个平台上写python的真的好少啊
n,m,k,p = map(int,input().split()) if n < 2&nbs***bsp;k < 1&nbs***bsp;m < 1&nbs***bsp;m > n&nbs***bsp;p < 1&nbs***bsp;p > n: print(0) dp = [0] * (n+1) dp[p-1] = 1 for i in range(k): leftup = dp[0] for j in range(n): temp = dp[j] if j == 0: dp[j] = dp[j+1]%100000007 elif j == n-1: dp[j] = leftup%100000007 else: dp[j] = (leftup + dp[j+1])%100000007 leftup = temp print(dp[m-1])
发表于 2020-08-08 15:50:41
回复(0)
C++一行辅助数组
#include <bits/stdc++.h>
using namespace std;
int main(){
int N, M, K, P;
cin>>N>>M>>K>>P;
vector<int> v(N+2, 0);
v[M] = 1;
int mod = 1e9 + 7;
while(K > 0){
K--;
int pre = 0;
for(int i=1;i<=N;++i){
int cur = (pre + v[i+1])%mod;
pre = v[i];
v[i] = cur;
}
}
cout<<v[P];
return 0;
}
就是前后补个0，完事儿v[i] = v[i-1] + v[i+1] 这里有个坑，就是pre作为存储前一个位置值的变量，要在每次循环时初始化为0
不然上一行的pre会影响到下一行第一个值，就只能过90%测试
发表于 2020-08-04 18:43:53
回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n, m, k, p;
cin >> n >> m >> k >> p;
vector<int> cur(n+2, 0);
vector<int> last(n+2,0);
int mod = 1e9 + 7;
last[m] = 1;
for(int step = 0; step < k; ++step){
for(int i = 1; i <= n; ++i){
cur[i] = (last[i-1] + last[i+1]) % mod;
}
for(int i = 1; i <= n; ++i) last[i] = cur[i];
}
cout << cur[p] << endl;
return 0;
}
发表于 2020-07-01 02:52:05
回复(0)
时间复杂度O(NK),空间复杂度压缩至O(N)。
import java.util.*;
public class Main {
public static final int mod = 1_000_000_007;
public static int process(int N, int M, int K, int P) {
int[] dp = new int[N + 1];
dp[P] = 1;
for (int k = 1; k <= K; k++) {
int upLeft = dp[1];
for (int i = 1; i <= N; i++) {
int tmp = dp[i];
if (i == 1)
dp[i] = dp[i + 1];
else if (i == N)
dp[i] = upLeft;
else
dp[i] = (upLeft + dp[i + 1]) % mod;
upLeft = tmp;
}
}
return dp[M];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // （2<=N<=5000）
int M = sc.nextInt();
int K = sc.nextInt(); // (1<=K<=5000)
int P = sc.nextInt();
int res = process(N, M, K, P);
System.out.println(res);
}
}
编辑于 2020-05-12 10:17:25
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
// 位置数n
int n = scanner.nextInt();
// 当前位置m
int m = scanner.nextInt();
// 只能走k步
int k = scanner.nextInt();
// 终点位置p
int p = scanner.nextInt();
System.out.println(getCount(n,m,k,p));
}
}
public static int getCount(int n, int m, int k, int p){
int mod = 1000000007;
int[][] dp = new int[k+1][n+1];
for(int i=1;i<=n;i++){
dp[0][i] = i == p ? 1 : 0 ;
}
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
if(j == 1){
dp[i][j] = dp[i-1][j+1];
}else if(j == n){
dp[i][j] = dp[i-1][j-1];
}else{
// 注意一定要在此处mod，而不是结尾return才mod
dp[i][j] = (dp[i-1][j+1]+dp[i-1][j-1]) % mod;
}
}
}
return dp[k][m];
}
}
发表于 2020-05-07 20:32:16
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int P = sc.nextInt();
System.out.println(search(N, M, K, P));
}
public static int search(int N, int M, int K, int P){
if(N < 2 || K <1 || M < 1 || M > N || P <1 ||P > N){
return 0;
}
int[][] dp = new int[K+1][N+1];
dp[0][P] = 1;
for(int i = 1; i <= K; i++){
for(int j = 1; j <= N; j++){
if(j==1){
dp[i][j] = dp[i-1][2] % (int)(1e9+7);
}else if(j == N){
dp[i][j] = dp[i-1][N-1] % (int)(1e9+7);
}else{
dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%(int)(1e9+7);
}
}
}
return dp[K][M] % (int)(1e9+7);
}
}
发表于 2020-04-26 10:56:13
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
