5600. 第 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        v, h = destination
        ans = list()

        for i in range(h + v):
            if h > 0:
                check = math.comb(h + v - 1, h - 1)
                if check < k:
                    k -= check
                    ans.append("V")
                    v -= 1
                elif check >= k:
                    ans.append("H")
                    h -= 1
            else:
                ans.append("V")
                v -= 1
        
        return "".join(ans)