题目分析

这个题目是231场周赛的第四题，题目难度并不大，需要小伙伴们仔细思考。

递归

要按照指令进行排序，可以想到的方法是遍历所有指令，使用DFS进行搜索，题目的row和column都是小于等于15的，在不剪枝的情况下有$2^{30}=1073741824$量级的计算量，在剪枝的情况下有$C_{30}^{15}=155117520$量级的计算量，一般在1e8以上时就会TLE，因此DFS无法求解。有兴趣的小伙伴们可以练习一下。

我们发现在一个row，column的地图中，一共有$$C_{row+col}^{row}$$种方案。前$$C_{row+col-1}^{col-1}$$种方案的第一个字符都是”H”，因为H的字典序排在前面，因此第一步一定是水平方向。因此我们每次只要判断一步该如何走，如果指令数小于等于$$C_{row+col-1}^{col-1}$$，那么第一步是水平方向，否则第一步为垂直方向，然后变成另一个更小地图的子问题即可。

在这里我又做了一些优化，如果小于等于$$ C_{row+col-1}^{col-1} $$，我们再判断是否小于等于$$ C_{row+col-i}^{col-i} $$，如果是，则一次可以向水平方向走i步。

算法的时间主要浪费在组合数的计算中，因此可以记忆化存储累积的结果，这样时间复杂度就会大大降低，**时间复杂度为$O(row+column)$，空间复杂度为$O(row+column)$**。

from functools import lru_cache


class Solution(object):
    def kthSmallestPath(self, destination, k):
        """
        :type destination: List[int]
        :type k: int
        :rtype: str
        """
        @lru_cache(None)
        def prod(x):
            if x <= 1:
                return 1
            return x * prod(x - 1)

        row, col = destination
        if k == 1:
            return 'H' * col + 'V' * row
        for i in range(col + row):
            c = prod(col - 1 - i + row) // prod(row) // prod(col - 1 - i)
            if k - 1 >= c:
                return 'H' * i + 'V' + self.kthSmallestPath([row - 1, col - i], k - c)

刷题总结

小伙伴们也可以经常打一打周赛，给定时间进行练习，代码功力不是看懂思路这么简单的，将自己的思路用代码的方式表达出来是一种更加重要的能力，希望小伙伴们不要眼高手低，一定要多写多练。