@ninijia 在 Leetcode每日一题练习 ------ 2684. 矩阵中移动的最大次数 中发帖
从Leetcode 每日一题练习继续讨论:
2684. 矩阵中移动的最大次数
2684. Maximum Number of Moves in a Grid
题解
本题每次移动时只能移动到自己后面一列的相邻三个方块内,而且必须移动到比当前方格内数字更大的方格中。则假如我们已知到当前方格的最长移动步数,再根据当前方格相邻方格的数字大小判断能否移动,将当前方格最长移动步数+1与相邻方格之前保存的最长步数比较即可知道相邻的几个方格的最长移动步数。在本题中,通过前一个方格的最长移动步数可以更新后面相邻方格的最长移动步数,因此大问题可以转换为从前一个方格移动到后面相邻方格过程中方格最长移动步数变化的小问题,这些小问题结构均相同。这样就可以通过循环,通过递推最终得到大问题的解。
具体而言,构造一个和矩阵大小相同的dp数组保存到某个方格的最长步数,因为题目限制起始方格只能在第一列,则先遍历第一列...