LeetCode688. Knight Probability in Chessboard——动态规划

这篇具有很好参考价值的文章主要介绍了LeetCode688. Knight Probability in Chessboard——动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).

A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly k moves or has moved off the chessboard.

Return the probability that the knight remains on the board after it has stopped moving.

Example 1:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.
Example 2:

Input: n = 1, k = 0, row = 0, column = 0
Output: 1.00000

Constraints:

1 <= n <= 25
0 <= k <= 100
0 <= row, column <= n - 1文章来源地址https://www.toymoban.com/news/detail-831519.html

二、题解

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(n,vector<vector<double>>(n,vector<double>(k+1,-1)));
        return f(n,row,column,k,dp);
    }
    //从(i,j)出发,还有k步要走,最后落在棋盘上的概率
    double f(int n,int i,int j,int k,vector<vector<vector<double>>>& dp){
        if(i < 0 || i >= n || j < 0 || j >= n) return 0;
        if(dp[i][j][k] != -1) return dp[i][j][k];
        double res = 0;
        if(k == 0) res = 1;
        else{
            res += (f(n,i-2,j+1,k-1,dp) / 8);
            res += (f(n,i-1,j+2,k-1,dp) / 8);
            res += (f(n,i+1,j+2,k-1,dp) / 8);
            res += (f(n,i+2,j+1,k-1,dp) / 8);
            res += (f(n,i+2,j-1,k-1,dp) / 8);
            res += (f(n,i+1,j-2,k-1,dp) / 8);
            res += (f(n,i-1,j-2,k-1,dp) / 8);
            res += (f(n,i-2,j-1,k-1,dp) / 8);
        }
        dp[i][j][k] = res;
        return res;
    }
};

到了这里,关于LeetCode688. Knight Probability in Chessboard——动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode——动态规划篇(二)

     刷题顺序及思路来源于代码随想录,网站地址:https://programmercarl.com  目录 343. 整数拆分 - 力扣(LeetCode) 96. 不同的二叉搜索树 - 力扣(LeetCode) 416. 分割等和子集 - 力扣(LeetCode) 1049. 最后一块石头的重量 II - 力扣(LeetCode)   给定一个正整数  n  ,将其拆分为  k  个 

    2024年02月07日
    浏览(34)
  • LeetCode —— 动态规划

    持续更新中..................................... 509. 斐波那契数 斐波那契数 (通常用  F(n)  表示)形成的序列称为 斐波那契数列 。该数列由  0  和  1  开始,后面的每一项数字都是前面两项数字的和。也就是:F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n 1。 示例: 输入: n

    2024年02月09日
    浏览(40)
  • LeetCode——动态规划篇(一)

    刷题顺序及思路来源于代码随想录,网站地址:https://programmercarl.com  目录 509. 斐波那契数 - 力扣(LeetCode) 70. 爬楼梯 - 力扣(LeetCode) 746. 使用最小花费爬楼梯 - 力扣(LeetCode) 62. 不同路径 - 力扣(LeetCode)  63. 不同路径 II - 力扣(LeetCode) 斐波那契数  (通常用  F(n)  表

    2024年02月09日
    浏览(36)
  • 【LeetCode】--- 动态规划 集训(一)

    题目地址: 1137. 第 N 个泰波那契数 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1 , 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n ,请返回第 n 个泰波那契数 Tn 的值。 示例 1: 输入:n = 4 输出:4 解释: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2: 输入:n = 25 输出:1389537 因为

    2024年03月25日
    浏览(49)
  • [LeetCode]-动态规划-4

    记录 LeetCode 刷题时遇到的动态规划相关题目,第四篇 枚举算法:首先对整个矩阵生成一个 row 数组,其中 row[i][j] 表示从 mat[i][j] 开始往左连续的 1 的个数 然后枚举的思路是,枚举所有的 mat[i][j],求以 mat[i][j] 为右下角的子矩形 的个数,然后求和,具体的求法是枚举以 mat[

    2024年01月24日
    浏览(39)
  • LeetCode——动态规划

    一、一维数组:斐波那契数列 爬楼梯70简单 dp定义: dp[i]表示爬到第i阶有多少种不同的方式 状态转移方程: dp[i] = dp[i-1] + dp[i-1] (每次可以爬1或2个台阶) 边界条件: dp[0] = 1; dp[1] = 1;(满足dp[2] = 2) 返回值: dp[n],即通过累积,dp[n]为爬到第n阶台阶的方式 改进: 因为dp只

    2024年02月03日
    浏览(57)
  • 【leetcode】动态规划::前缀和

    标题:【leetcode】前缀和 @水墨不写bug 正文开始: 给定一个长度为n的数组a1​,a2​,....an​. 接下来有q次查询, 每次查询有两个参数l, r. 对于每个询问, 请输出al​+al+1​+....+ar​ 输入描述: 第一行包含两个整数n和q. 第二行包含n个整数, 表示a1​,a2​,....an​. 接下来q行,每行包含

    2024年04月11日
    浏览(41)
  • leetcode 动态规划(单词拆分)

    139.单词拆分 力扣题目链接(opens new window) 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = “leetcode”

    2024年02月22日
    浏览(41)
  • Leetcode 刷题 动态规划

    309. 最佳买卖股票时机含冷冻期 1. 确定dp数组以及下标的含义 具体可以区分出如下四个状态: 状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有) 不持有股票状态,这里就有两种卖出股票状态 状态二:保持卖出股票的状态(两天前就

    2024年02月11日
    浏览(46)
  • leetcode-动态规划【背包问题】

    基础背包: 416. 分割等和子集 1049. 最后一块石头的重量ii 494. 目标和 474. 一和零 完全背包: 518. 零钱兑换ii 377. 组合总和iv 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包: n件物品和最大承受重量为w的背包,其中第i件物品的重量是weight[i],得到的价值是val

    2023年04月08日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包