文章目录
一、问题分析
二、代码示例
骑士的最短路径 II :
在 国际象棋 中 , 骑士 类似 与 象棋 中的 马 , 走 " 日 " 字 格子 ;
骑士有 8 种走法 : " 日 " 字 格子 ,...黑色是 骑士的初始位置 ( 0 , 0 ) , 绿色 和 红色 是 骑士 可以走的 下一步位置 ;
给定一个二维坐标 , 在该坐标系中 , 骑士只能走 上图中 右边 红色的四个方向的步骤 , 计算从...左上角 到 右下角 的最短路径数 ;
一、问题分析
----
如果 骑士 可以走 8 个方向 ,
那么需要 使用 BFS 宽度优先搜索 算法 ;
此时 不能使用 动态规划解决上述问题 , 如果 可以走...8 个方向 , 那么路径就可以反复 , 会出现 循环依赖的情况 ;
如果 骑士 只能走右边的 4 个方向 , 没有循环依赖 , 则可以使用动态规划 , 解决上述问题 ;
如果 骑士 只能走 右侧的 四个方向...;
如果 算法求的是 方案数 , 则初始化状态值时 , 可以初始化为 0 ;
二、代码示例
----
代码示例 :
class Solution {
// 根据骑士只能向右的四个方向 , 走到
