写在前面

这周周赛的最后一道题，其实难度不是很大，而且第K问题是很经典的，还是我做过的问题，但是当时脑子就是转不过来个，怎么都想不出来，只想到了暴力枚举，TLE收了尾。。。

题目

比赛里看了题目数据范围最大只有15，一个激动直接O(2^N)暴力搜索，结果要行列同时考虑，相当于数据范围在30左右，直接就超时了。

核心思路

由于起点终点确定，代表了我们向右移动的步数和向下移动的步数都已经固定为h 和 v，那么题目求解的就是在 h个H和v个V的组合中第K小的字符串。
如果我们考虑当前位置 i (i之前已经确定)应该是什么字符，由于H小于V，所以可以想到所有当前位置是H的字符串都小于当前位置是V的字符串，那么如果我们知道当前位置是H的字符串的数量，再与目标k进行比较，就可以明确的确定当前位置到底是H 还是 V 了。
那么这个数该怎么求呢？根据排列组合思想，如果当前位置还不放字符时H和V的数量分别为 h 和 v ，那么当前位置取H对应的组合数就是nCr(h - 1 + v, h - 1)，所以我们不妨提前算出题目范围的所有组合数，然后根据上边的思路逐个位置确定该放什么字符即可。

完整代码

class Solution {

    int[][] C;

    public String kthSmallestPath(int[] destination, int k) {
        int h = destination[1];
        int v = destination[0];
        C = new int[h + v + 1][h + v + 1];
        C[0][0] = 1;
        for(int i = 1; i <= h + v; i++){
            C[i][0] = 1;
            for(int j = 1; j <= i; j++)
                C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }

        String res = "";
        int all = h + v;
        for(int i = 0; i < all; i++){
            if(h > 0){
                int num = C[h + v - 1][h - 1];
                if(k > num){
                    res += 'V';
                    v--;
                    k -= num;
                }else{
                    res += 'H';
                    h--;
                }
            }else{
                res += 'V';
                v--;
            }
        }
        return res;
    }
}

因为数据范围比较小，直接使用杨辉三角递推求组合数即可。对于求出的组合数，如果k比较大的话，说明第k条指令的当前位置应该以V开头，反之应该以H开头。
这道题真的越看越觉得眼熟，但是就是想不起来是哪道题、怎么做了，自己思路还是不够开拓啊，一点点继续努力加油了。如果文章有写的不正确的地方还请指出，感恩相遇~~