C++ [DP + binSearch] [Easy to Understand]
First build a dp array where dp[v][h] denotes the count of permutation given v V\'s and h H\'s.\n\nThen perform a \'binary search\'. We will decide from left to
First build a dp array where **dp[v][h]** denotes the count of permutation given v **V**\'s and h **H**\'s.\n\nThen perform a \'*binary search*\'. We will decide from left to right the next char to push back into the answer. \n\nSuppose now we have h \'**H** and v \'**V**\'\'s. If next character is \'**V**\' then we are throwing away all the permutations that has \'**H**\' in the same location, the number of solutions is **dp[v][h-1]**. Therefore, if k is greater than **dp[v][h-1]** then the next char is **\'V**\', otherwise it is \'**H**\'.\n\nComlexity should be **O(V*H)** which is the cost to build the dp array.\n\n```\nclass Solution {\npublic:\n    string kthSmallestPath(vector<int>& destination, int k) {\n        int v = destination[0];  // num of V\n        int h = destination[1];  // H\n        vector<vector<int>> p(v+1, vector<int>(h+1, 0));\n        for (int i = 0; i <= h; ++i) {\n            p[0][i] = 1;\n        }\n        for (int j = 0; j <= v; ++j) {\n            p[j][0] = 1;\n        }\n        for (int i = 1; i <= v; ++i) {\n            for (int j = 1; j <= h; ++j) {\n                p[i][j] = p[i-1][j] + p[i][j-1];\n            }\n        }\n        string res = "";\n        while (k > 0) {\n            // if next char is V we will throw away p[r][c-1] solutions\n            if (v > 0 && k > p[v][h-1]) {\n                k -= p[v][h-1];\n                res.push_back(\'V\');\n                --v;\n            } else {\n                res.push_back(\'H\');\n                --h;\n            }\n            if (v == 0 && h != 0) {\n                res += string(h, \'H\');\n                return res;\n            } else if (h == 0 && v != 0) {\n                res += string(v, \'V\');\n                return res;\n            } else if (h == 0 && v == 0) break;\n        }\n        return res;\n    }\n};\n```
[]