动态规划的题目需求各异，想法也差别比较大，有时候找出状态转移方程并不是那么容易的事情，需要具体问题具体分析。今天这篇文章将要下大家介绍一种新的基于动态规划解决的题目，并辅以自己的分析思路的阐述过程，欢迎读者基于此提出问题意见和建议。
题目的内容如下：给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。返回一个表示可访问单元格最大数量的整数。
下面简要阐述一下我的思路分析以及一个不错的参考答案：
可能的思路1：我们先只针对问题本身，而不是提示解决的具体方法去尝试分析问题，我们可以针对矩阵的每个位置(i,j)去找到它的该行和列的可能路径(row[i][j]，为矩阵当前行中比当前单元格mat[i][j]值要大的元素的集合，同理可以找出col[i][j]),矩阵中每个元素找出之后，就可以通过树搜索的方式，找出mat[i][j]所有可能路径中最大的(搜索树中从根节点到叶子节点的最大路径数字，经过简单验证可以得出当前位置在同一行和同一列的candidate中，必然要经过同行或者同列中比它大的最小的值，因为其他大的值可以通过这个值去抵达，因此同行和同列中的大的元素可以增序进行排列，而且可以以一颗二叉树来进行构建搜索树，按行行走为左子树，按列行走为右子树）。但是问题是要针对每个元素去找这样的最大路径，所需要的时间复杂度肯定就比较高。当然也可以不用每个元素都要调用这样的搜索树，可以基于已经搜索出来的和相邻节点的大小关系算出附近节点所能访问的单元格的最大数量。还有基于当前节点去遍历的这颗最大路径和上的路径上的每一个节点的最大值也是确定的（不仅如此，每一个路径节点的值都是最大值）。这样也可以基于此去优化搜索过程。
可能的思路2（参考答案）：基于思路1，可以进行进一步的优化，基于整个矩阵可以建立一颗有向无环图（不一定是树），同一行（列）中按节点顺序构造有向边(如果存在同一行或列有相同值的时候，可以加入一个dummy节点)，然后基于有向无环图（不一定联通，可能有多个分量组成）去找到最长的路径，具体可以用动态规划的算法，后面有时间再介绍详细动态规划实现上的细节。
可能的思路3：基于初始值的多次迭代更新后收敛，比如每个元素位置的初始值可以设为其行和列中比它大的数字的个数的最大值。然后更新的规则是当前行和列中比它大的值的位置对应值里边的最大值加1，不断这个过程直至每个位置对应的结果值不再发生变化。
以上主要从解决思路上分别做了阐述，欢迎读者点评，如有逻辑问题欢迎读者批评指正，或者分享新的解题思路，谢谢。
References
Leave a Reply