lt 5600. 第 K 条最小指令 （组合数+思维）

本文主要是介绍lt 5600. 第 K 条最小指令 （组合数+思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第 K 条最小指令

思路
优先确定高位 + 组合计数
首先，此题可以转化为排列h个H和v个V组成字符串集合中，第k小的字符串是哪一个？

考虑最高位是放 H 还是 V。由于后者的字典序较大，因此如果最高位放 V，那么所有最高位为H 的字符串的字典序都比它小，这样的字符串共有n = c[h + v - 1][h - 1]个。即就是确定了最高位为 H，剩余 h+v-1个位置中选择 h-1 个放入 H，其余位置自动放入 V 的方案数。因此：

1. 如果 k大于这个组合数 n，那么最高位一定是 V。我们将 v 减少 1，并且需要将 k -=n，这是因为剩余部分应当是包含 (h,v-1)的字典序第 k-n小的字符串；

2. 如果 k 小于 n，那么最高位是 H。我们将 h 减少 1，但我们不需要改变 k的值，这是因为剩余部分就是包含 (h-1,v)的字典序第 k 小的字符串。

这样一来，我们就可以从高位开始，依次确定每一个位置的字符了。需要注意的是，当 h=0时，我们只能放V，无需进行判断。

Python 语言，可以使用 math.comb() 方便地求出组合数.
或者用组合数的递推式预处理
c[n][k] = c[n-1][k-1] + c[n-1][k]

class Solution:def kthSmallestPath(self, destination: List[int], k: int) -> str:h = destination[1]v = destination[0]res = []for i in range(h + v):if h > 0:n = math.comb(h + v - 1, h - 1)if k > n:k -= n v -= 1res.append("V")else:h -= 1res.append("H")else:v -= 1res.append("V")return "".join(res)

这篇关于lt 5600. 第 K 条最小指令 （组合数+思维）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---