深度剖析动态规划算法求解跳跃游戏_小明最近在研究一个棋盘游戏,游戏规则如下: 一个n*n的棋盘,每个格子里面填写有1、

作者：AllinToyou | 2024-03-17 02:37:44

踩

小明最近在研究一个棋盘游戏,游戏规则如下: 一个n*n的棋盘,每个格子里面填写有1、

深度剖析动态规划算法求解跳跃游戏

题目描述：在一个N*N大小的棋盘中，每个格子都标有1到9当中的一个整数。游戏规则是，从棋盘的最左上角出发，最终到达最右下角。在此过程中，按照相应数值的大小可以向右或者向下移动，但是不能走出棋盘。关键在于，给定标有数值的棋盘时，判断出有没有达到终点的方法。如下如所示：

这个问题如何求解？

求解思路

从左上角起点开始搜索所有可能的走法，利用递归调用很容易实现算法。假设实现跳跃的方法为jump，则：

jump(y,x) = 返回 “从（y，x）起始能否达到终点”

每调用一次jump()，将选择从当前位置向右移动还是向下移动。假设棋盘位置（y，x）的数值是jumpSize，那么：

向下移动时能够达到终点就可以表示为jump（y+jumpSize，x）；

向右移动时能够达到终点就

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/253495