力扣1643题解：贪心算法与组合数的完美结合

一、问题理解

我们需要构造从起点到终点的路径指令，满足：

1. 只能向右或向下移动

2. 所有可能路径按字典序排列

3. 找到第k小的路径指令

二、算法设计思路

1. ‌组合数学基础‌：理解路径总数是组合数C(h+v,h)

2. ‌字典序特性‌：'H'在字典序上小于'V'

3. ‌贪心构造‌：每一步根据剩余k值决定选择方向

三、实现代码

class Solution {
public:
    string kthSmallestPath(vector<int>& destination, int k) {
        int v = destination[0]; // 需要向下走的次数
        int h = destination[1]; // 需要向右走的次数
        string res;
       
        // 预计算组合数C(n,k)
        vector<vector<int>> comb(h + v, vector<int>(h + v, 0));
        for (int i = 0; i < h + v; ++i) {
            comb[i][0] = 1;
            for (int j = 1; j <= i; ++j) {
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
            }
        }
       
        while (h > 0 && v > 0) {
            // 如果选择'H'，后面有C(h+v-1, h-1)种可能
            int c = comb[h + v - 1][h - 1];
            if (k <= c) {
                res += 'H';
                h--;
            } else {
                res += 'V';
                k -= c;
                v--;
            }
        }
        // 处理剩余全部'H'或'V'的情况
        res += string(h, 'H');
        res += string(v, 'V');
        return res;
    }
};

四、关键实现细节

1. ‌组合数计算‌：使用动态规划预计算避免重复计算

2. ‌路径构造策略‌：优先尝试'H'，减少k值

3. ‌边界处理‌：当只剩一个方向时的快速处理