• 数据库
  • Mysql
  • Nosql
  • 技术框架
  • Spring
  • Kafka
  • ibatis
  • 分布式
  • Linux
  • 关于我们
  • 注册
  • 登录
  • 递归DP-机器人到达目的地方法数

    2022-6-5 diaba 笔试题

    package com.jiucaiyuan.net.question;
    
    /**
     * @Author jiucaiyuan  2022/6/5 10:34
     * @mail services@jiucaiyuan.net
     */
    
    public class Rabbit {
    
        /**
         * 给了一个固定值n,表示总共有多少个位置
         * 开始机器人在s位置上,每次可以迈一步,想要到达e位置,总共要走k步,有多少种走法可以到达e位置
         * 机器人可以往左走,也可以往右走
         *
         * @param n 总共位置数  1 2 3 4 ... n
         * @param s start开始位置(机器人开始停在s位置)
         * @param e end目标位置 (迈k步后,停留在e位置)
         * @param k 迈的步数 (机器人必须走k步)
         * @return 总共走法的种数
         */
        public static int walkWays(int n, int s, int e, int k) {
            return process(n, e, k, s);
        }
    
        /**
         * 暴力递归实现
         * 因为递归过程类似一个二叉树的遍历,高度为k,所以时间复杂度是 O(2^k)
         *
         * @param n    总共位置1 2 3 4 5 ... n
         * @param e    目标位置
         * @param rest 当前剩下的步数
         * @param curr 当前所在的位置
         * @return 当前的走法数目
         */
        public static int process(int n, int e, int rest, int curr) {
            //当前没有步骤可走了,如果在目标位置上,那么找到1中走法,如果没有在目标位置上,不是合法走法
            if (rest == 0) {
                return curr == e ? 1 : 0;
            }
            //如果当前位置在1,那么只能往2位置走
            if (rest == 1) {
                return process(n, e, rest - 1, 2);
            }
            //如果当前位置在n,那么下一步只能走到n-1
            if (rest == n) {
                return process(n, e, rest - 1, n - 1);
            }
            //如果不在第一个位置,也不在最后一个位置,那么可以向左走一步,也可以往右走一步
            return process(n, e, rest - 1, curr - 1) + process(n, e, rest - 1, curr + 1);
        }
    
        /**
         * 给了一个固定值n,表示总共有多少个位置
         * 开始机器人在s位置上,每次可以迈一步,想要到达e位置,总共要走k步,有多少种走法可以到达e位置
         * 机器人可以往左走,也可以往右走
         * 优化版本,暴力递归中重复的操作用缓存空间换时间的方式优化掉
         *
         * @param n 总共位置数  1 2 3 4 ... n
         * @param s start开始位置(机器人开始停在s位置)
         * @param e end目标位置 (迈k步后,停留在e位置)
         * @param k 迈的步数 (机器人必须走k步)
         * @return 总共走法的种数
         */
        public static int walkWaysV2(int n, int s, int e, int k) {
            int[][] dp = new int[k + 1][n + 1];
            for (int i = 0; i <= k; i++) {
                for (int j = 0; j <= n; j++) {
                    dp[i][j] = -1;
                }
            }
            return processV2(n, e, k, s, dp);
        }
    
        /**
         * 用空间换取暴力递归中重复计算的一些值
         * 时间复杂度: O(k*n)
         *
         * @param n    总共位置1 2 3 4 5 ... n
         * @param e    目标位置
         * @param rest 当前剩下的步数
         * @param curr 当前所在的位置
         * @param dp   计算过的值记录起来
         * @return 当前的走法数目
         */
        public static int processV2(int n, int e, int rest, int curr, int[][] dp) {
            if (dp[rest][curr] != -1) {
                return dp[rest][curr];
            }
            //当前没有步骤可走了,如果在目标位置上,那么找到1中走法,如果没有在目标位置上,不是合法走法
            if (rest == 0) {
                dp[rest][curr] = curr == e ? 1 : 0;
            } else if (rest == 1) {
                //如果当前位置在1,那么只能往2位置走
                dp[rest][curr] = process(n, e, rest - 1, 2);
            } else if (rest == n) {
                //如果当前位置在n,那么下一步只能走到n-1
                dp[rest][curr] = process(n, e, rest - 1, n - 1);
            } else {
                //如果不在第一个位置,也不在最后一个位置,那么可以向左走一步,也可以往右走一步
                dp[rest][curr] = process(n, e, rest - 1, curr - 1) + process(n, e, rest - 1, curr + 1);
            }
            return dp[rest][curr];
        }
    
        /**
         * 动态规划方式实现
         * 其实是分析上述递归过程,发现递归过程的规律,改为二维数组dp的前后联系,转化为dp二维数组的求解过程
         * (动态转移方程,其实就是上述递归的过程,也是分析尝试的过程)
         * 时间复杂度 O(k*n)
         *
         * @param n 总共可选位置1 2 3 4 ... n
         * @param e 目标位置
         * @param s 开始位置
         * @param k 需要移动步数
         * @return 返回走法数目
         */
        public static int dpWay(int n, int e, int s, int k) {
            int[][] dp = new int[k + 1][n + 1];
            dp[0][e] = 1;
            for (int rest = 1; rest <= k; rest++) {
                for (int curr = 1; curr <= n; curr++) {
                    if (curr == 1) {
                        dp[rest][curr] = dp[rest - 1][2];
                    } else if (curr == n) {
                        dp[rest][curr] = dp[rest - 1][curr - 1];
                    } else {
                        dp[rest][curr] = dp[rest - 1][curr - 1] + dp[rest - 1][curr + 1];
                    }
                }
            }
            return dp[s][k];
        }
    }
    

    发表评论:

  • 最新文章

  • Go-数组,切片,map
  • scp拷贝文件
  • 笔试题-牛羊吃草问题
  • 笔试题-最少的袋子数装苹果
  • 递归DP-找零钱的方法数
  • 存档

  • 2022年10月(1)
  • 2022年8月(1)
  • 2022年6月(11)
  • 2022年5月(6)
  • 2022年4月(33)
  • 2022年3月(26)
  • 2021年3月(1)
  • 2020年9月(2)
  • 2018年8月(1)
  • 2018年3月(1)
  • 2017年3月(3)
  • 2017年2月(6)
  • 2016年12月(3)
  • 2016年11月(2)
  • 2016年10月(1)
  • 2016年9月(3)
  • 2016年8月(4)
  • 2016年7月(3)
  • 2016年6月(4)
  • 2016年5月(7)
  • 2016年4月(9)
  • 2016年3月(4)
  • 2016年2月(5)
  • 2016年1月(17)
  • 2015年12月(15)
  • 2015年11月(12)
  • 2015年10月(6)
  • 2015年9月(11)
  • 2015年8月(8)
  • 分类

  • Java(4)
  • 基础(8)
  • IO(3)
  • JVM(7)
  • 多线程(11)
  • 调优命令(1)
  • Go(0)
  • 基础(1)
  • Linux(10)
  • mac(12)
  • 数据库(2)
  • Mysql(7)
  • Nosql(8)
  • 技术框架(2)
  • Spring(5)
  • Kafka(3)
  • ibatis(2)
  • 分布式(4)
  • 数据结构与欧宝安德拉(0)
  • 数据结构(6)
  • 欧宝安德拉(44)
  • 笔试题(19)
  • emlog(1)
  • 问题解决记录(2)
  • 随笔记录(26)
  • 金融(1)
  • 工具使用(8)
  • 操作系统(3)
  • 用友NC(3)
  • NC常见问题(2)
  • 热门文章

  • SpringMVC:Null ModelAndView returned to DispatcherServlet with name 'applicationContext': assuming HandlerAdapter completed request handling
  • Mac-删除卸载GlobalProtect
  • java.lang.SecurityException: JCE cannot authenticate the provider BC
  • Idea之支持lombok编译
  • MyBatis-Improper inline parameter map format. Should be: #{propName,attr1=val1,attr2=val2}
  • 标签

    mac emlog NC授权 授权数 用户数 破解 天上一天 redis 已达授权数 用友NC 可打印 地上一年 超光速 大于光速 时间静止 时光倒流 相对论 go基础 shell CountDownLatch 狱中诗 线程同步 任务同步 SecureCRT 光标消失 做人 做事 职业发展 选人 转义字符 json 格式错误 内存分区 操作系统 cache 分布式 程序 Linux crontab 定时任务 license 安全 备份 IO操作 同步 异步 阻塞 进程 线程 并发 共享内存 mybatis Improper inline 数据库 mysql 如果为null query paxos 分布式一致性 if ifnull spring ioc BlockingQueue OOM 软引用 弱引用 并行 jvm参数 gc jvm kafka 2016 数据库引擎 加密 解密 java文件压缩 命令 RDB AOF 配置 调优 sharding jvm结构 存储引擎 myiasm innodb 乐观锁 悲观锁 理财 欧宝安德拉 异地多活 ctrl+alt+delete idea lombok springmvc aes 宝宝 项目经理 nc curl 按位操作 逻辑思维 excel 原子增操作 awk printf OceanBase mac锁屏 快捷键 文件监听 confict git 商品管理 sku 自动注入 Apple ID Javassist branch 正则表达式 参数必填 代码优化 grep 程序员 未来 保险 坦然生活 抗风险 优秀经纪人 汉诺塔 递归
  • 最新评论

  • logisqykyk
    Javassist分析、编辑和创建jav...
  • xxedgtb
    Redis—常见参数配置 - 韭菜园 ...
  • wdgpjxydo
    SpringMVC:Null Model...
  • rllzzwocp
    Mysql存储引擎MyISAM和Inno...
  • dpkgmbfjh
    SpringMVC:Null Model...
  • tzklbzpj
    SpringMVC:Null Model...
  • bqwrhszmo
    MyBatis-Improper inl...
  • 乐谱吧
    good非常好
  • diaba
    @diaba:应该说是“时间的度量依据”...
  • diaba
    如果速度增加接近光速、等于光速、甚至大于...
  • 最新微语

  • 从今天起,做一个幸福的人。喂马,砍柴,(思想)周游世界

    2022-03-21 23:31

  • 2022.03.02 23:37:59

    2022-03-02 23:38

  • 几近崩溃后,找到解决方法,总是那么豁然开朗!所以遇到问题要坚持!

    2018-07-18 10:49

  • 2018年关键字“走心”

    2018-03-19 16:07

  • 保护好自己最大的方法是让自己更强大,不要柔弱的像一只绵羊一样,得谁巴拉,就谁巴拉!

    2017-12-20 10:24

  • 更多»

    Powered by emlog 京ICP备15045175号-1 Copyright © 2022