文章目录
一、问题分析
二、代码示例
骑士的最短路径 II :
在 国际象棋 中 , 骑士 类似 与 象棋 中的 马 , 走 " 日 " 字 格子 ;
骑士有 8 种走法 : " 日 " 字 格子 ,...8 个方向 , 那么路径就可以反复 , 会出现 循环依赖的情况 ;
如果 骑士 只能走右边的 4 个方向 , 没有循环依赖 , 则可以使用动态规划 , 解决上述问题 ;
如果 骑士 只能走 右侧的 四个方向...1 列 ;
那么 如果当前位置是 ( i , j ) , 那么当前位置的 最短路径 是 dp[i][j] , 那么该点的 最短路径 依赖于 如下几个点的最短路径 :
( i + 2 , j - 1...起始点 ( 0 , 0 ) 位置 跳转到 ( i , j ) 位置的 最短路径数 ;
该算法求的是 最短路径数 , 初始化 状态 值 时 , 不能初始化为 0 , 这里 初始化为 Integer.MAX_VALUE...{
// 根据骑士只能向右的四个方向 , 走到 (i, j) 点的最短路径, 需要依赖
// ( i + 2 , j - 1 )
// ( i + 1 , j - 2 )