[LeetCode] 1643. 第 K 条最小指令

Bob 站在单元格 (0, 0) ，想去目的地 destination ：(row, column) 。他只能向 右 或向 下 走吧。你可以 Bob 提供导航 指令 帮他到达目的地 destination 。

指令 每个字符都用字符串表示:

‘H’ ，意味着水平向右移动 ‘V’ ，意味着竖直向下移动 能够为 Bob 导航到目的地 destination 如果目的地有多种指令，例如 destination 是 (2, 3)，“HHHVV” 和 “HVHVH” 都是有效 指令 。

然而，Bob 很挑剔。因为他的幸运数字是 k，他想要遵循 按字典顺序排列后的第 k 条最小指令 导航到目的地 destination 。k 的编号 从 1 开始 。

给你一个整数数组 destination 和一个整数 k ，请返回 Bob 提供到目的地 destination 导航的 按字典顺序排列后的第 k 条最小指令 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-smallest-instructions 作权归网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 给 a a a个 H H H, b b b个 V V V, 在所有字符串中，字典序第k小串。
2. 第一个元素是固定的 H H H，总共有 C a b ? 1 a ? 1 C_{a b-1}^{a-1} Ca b?1a?1个元素， 第一个为 V V V , 总共有 C a b ? 1 a C_{a b-1}^{a} Ca+b−1a​个元素。 根据k的大小，我们就知道了第一个元素是什么。依次判断每一个元素就可以了
3. 可能出现计算组合数占用的时间太长的问题，避免重复计算，我们可以用缓存中间的技术。 C n r = n r C n − 1 r − 1 C_{n}^{r} = \frac{n}{r}C_{n-1}^{r-1} Cnr​=rn​Cn−1r−1​

from functools import lru_cache
class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        b, a = destination
        @lru_cache
        def C(n, r):
            if r == 0: return 1
            return n * C(n - 1, r - 1) / r
        
        def solve(a, b,k, ret):
            if a == 0: return ret + ("V" * b)
            if b == 0: return ret + ("H" * a)
            if k > C(a+b-1, a-1):
                return solve(a, b-1, k - C(a+b-1, a-1), ret + "V")
            else:
                return solve(a - 1, b, k , ret + "H")
        
        return solve(a, b , k , "")