首页 > 试题广场 >

机器人达到指定位置方法数

[编程题]机器人达到指定位置方法数

热度指数：7822 时间限制：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

输出

说明

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

说明

注意答案要取模

备注:

时间复杂度,空间复杂度。

算法知识视频讲解

Java

pein531

我们先可以分析这个过程，记机器人当前的位置为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步，时间复杂度就是2^k指数级别，当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时，它依赖的是右上角的位置，因此状态转移方程为： $dp[rest][cur] = dp[rest - 1][cur + 1]$
当cur=n时，它依赖的是左上角的位置，因此状态转移方程为： $dp[rest][cur] = dp[rest - 1][cur - 1]$
当1<cur<n时，它依赖的是左右上角之和，因此状态转移方程为： $dp[rest][cur] = dp[rest - 1][cur - 1] + dp[rest - 1][cur + 1]$

然后改出动态规划的版本，但时间复杂度相比记忆化搜索并没有提升

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)

Java

jahentao

时间复杂度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)

Java

zyf天下

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)

提交观点

问题信息

动态规划

上传者：小小

难度：

3条回答 46收藏 8243浏览

通过挑战的用户

查看代码

普信员

2023-02-27 07:28:22
鼠鼠_本鼠

2023-02-23 20:08:00
隐隐蓝海

2023-02-14 19:11:26
One Peach

2023-02-03 16:34:24
向回走的闹钟

2023-01-13 14:49:47

机器人达到指定位置方法数

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题