leetcode688. 骑士在棋盘上的概率(java)

这篇具有很好参考价值的文章主要介绍了leetcode688. 骑士在棋盘上的概率(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode688. 骑士在棋盘上的概率

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/knight-probability-in-chessboard

题目描述

在一个 n x n 的国际象棋棋盘上,一个骑士从单元格 (row, column) 开始,并尝试进行 k 次移动。行和列是 从 0 开始 的,所以左上单元格是 (0,0) ,右下单元格是 (n - 1, n - 1) 。
象棋骑士有8种可能的走法,如下图所示。每次移动在基本方向上是两个单元格,然后在正交方向上是一个单元格。

leetcode688. 骑士在棋盘上的概率(java)每次骑士要移动时,它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘),然后移动到那里。
骑士继续移动,直到它走了 k 步或离开了棋盘。
返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

示例 1:
输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2),(2,1))可以让骑士留在棋盘上。
在每一个位置上,也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。

示例 2:
输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000

提示:
1 <= n <= 25
0 <= k <= 100
0 <= row, column <= n - 1

解题思路

递归去解决这个问题。八个方向递归。
每次走步数减一。
base case .步数为0 时,和走出棋盘时,都停止,

注意:
直接暴力递归,会超时,跑不过去,需要加上缓存,

代码演示

 public double knightProbability(int n, int k, int row, int column) {
        double[][][]dp = new double[n][n][k+1];
          
        return process(n,k,row,column,dp);    
    }


    public double process(int n ,int k,int row,int column,double[][][]dp){
    		//抛出棋盘外,直接停止
        if(row >= n || row < 0 || column >= n || column < 0){
            return 0.0;
        }
        //缓存有值时 从缓存里拿值
        if( dp[row][column][k] != 0){
            return dp[row][column][k];
        }
        //步数走完,走出棋盘外的情况已经在上面拦截,到这里的都是棋盘内的,直接返回1
        if(k == 0){
            return 1.0;
        }
        double ori = 0.125;
        //八个方向递归
        double p1 = ori * process(n,k-1,row-2,column+1,dp);
        p1 += ori * process(n,k-1,row-1,column+2,dp);
        p1 += ori * process(n,k-1,row+1,column+2,dp);
        p1 += ori * process(n,k-1,row+2,column+1,dp);

        p1 += ori * process(n,k-1,row+2,column-1,dp);
        p1 += ori * process(n,k-1,row+1,column-2,dp);
        p1 += ori * process(n,k-1,row-1,column-2,dp);
        p1 += ori * process(n,k-1,row-2,column-1,dp);
        dp[row][column][k] = p1;
        return p1;
    }

动态规划专题

leetcode.486. 预测赢家

leetcode1143. 最长公共子序列

最长回文子序列

象棋里马走到指定位置的方法数

最小路径和

凑零钱.钱币的组合有多少种文章来源地址https://www.toymoban.com/news/detail-476533.html

到了这里,关于leetcode688. 骑士在棋盘上的概率(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 1093. Statistics from a Large Sample【数学,概率与统计】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月06日
    浏览(38)
  • ​LeetCode解法汇总1080. 根到叶路径上的不足节点

    https://github.com/September26/java-algorithms 给你二叉树的根节点  root  和一个整数  limit  ,请你同时删除树中所有  不足节点  ,并返回最终二叉树的根节点。 假如通过节点  node  的每种可能的 “根-叶” 路径上值的总和全都小于给定的  limit ,则该节点被称之为  不足节点 

    2024年02月06日
    浏览(36)
  • LeetCode 周赛 347(2023/05/28)二维空间上的 LIS 最长递增子序列问题

    本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 往期回顾:LeetCode 单周赛第 346 场 · 仅 68 人 AK 的最短路问题 T1. 移除字符串中的尾随零(Easy) 标签:模拟、字符串 T2. 对角线上不同值的数量差(Easy) 标签:前后缀分解 T3. 使所有字符相等的最小

    2024年02月06日
    浏览(51)
  • 《算法竞赛·快冲300题》每日一题:“超级骑士”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 超级骑士 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1810 【题目描述】 现在在一个无

    2024年02月17日
    浏览(51)
  • leecode 每日一题 2596. 检查骑士巡视方案

      2596. 检查骑士巡视方案 骑士在一张  n x n  的棋盘上巡视。在  有效  的巡视方案中,骑士会从棋盘的  左上角  出发,并且访问棋盘上的每个格子  恰好一次  。 给你一个  n x n  的整数矩阵  grid  ,由范围  [0, n * n - 1]  内的不同整数组成,其中  grid[row][col]  表示单

    2024年02月08日
    浏览(46)
  • java算法之Math.random()随机概率玩法

    java中的Math.random()是一个在[0,1)范围等概率返回double数值类型的算法,基于此函数,我们来延申一些随机概率算法的变形思路,便于大家对Math.random()函数的随机概率理解 Math.random()返回的数据范围是[0,1) Math.random()数据是等概率返回 Math.random()返回的数据类型是double 我们可以通

    2023年04月26日
    浏览(33)
  • 阿里云如何完全卸载阿里云盾(安骑士)并屏蔽阿里云盾IP

    为什么买了服务器之后明明什么都没有配置,阿里云却会给你推送服务器的危险消息?如何解决这个问题? 阿里云盾(AliYunDun),又名阿里云安骑士,是阿里云自带的云监控软件,自动帮你监控阿里云服务器或者轻量应用服务器的状态,以及监控你的服务器是否有违规进程,

    2024年02月02日
    浏览(31)
  • 【Unity实战】制作类元气骑士、挺进地牢——俯视角射击游戏多种射击效果(二)

    参考原视频链接 : 【视频】:https://space.bilibili.com/641773200 注意 :本文为学习笔记记录,推荐支持原作者,去看原视频自己手敲代码理解更加深入

    2024年02月12日
    浏览(51)
  • 棋盘问题

    【问题描述】 小蓝拥有 n × n 大小的棋盘,一开始棋盘上全都是白子。小蓝进行了m次操作,每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色,黑色棋子变为白色)。 请输出所有操作做完后棋盘上每个棋子的颜色。 【输入格式】 输入的第一行包

    2024年02月04日
    浏览(29)
  • 棋盘覆盖问题——分治法

    问题描述 有一个 xlt;img src=\\\"https://latex.codecogs.com/gif.latex?2%5Ek\\\" alt=\\\"2^k\\\" class=\\\"mathcode\\\" /gt;amp;nbsp;(kamp;gt;0)的棋盘,恰好有一个方格与其他方格不同,称之为特殊方格。现在要用如下图所示的L形骨牌覆盖除了特殊方格以外的其他全部方格,骨牌可以任意旋转,并且任何两个骨牌

    2023年04月26日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包