【題解】LeetCode 1643. Kth Smallest Instructions

class Solution {
public:
    string kthSmallestPath(vector<int>& d, int k) {
        int n = d[0]+1, m = d[1]+1;
        int dp[20][20] = {};
        for (int i = 0; i < m; i++){
            dp[n-1][i] = 1;
        }
        for (int i = n-2; i >= 0; i--){
            for (int j = m-1; j >= 0; j--){
                dp[i][j] = dp[i+1][j]+dp[i][j+1];
            }
        }
        int x = 0, y = 0;
        string ans;
        for (int i = 0; i < n+m-2; i++){
            if (x == n-1){
                y++;
                ans += 'H';
            }
            else if (y == m-1){
                x++;
                ans += 'V';
            }
            else{
                if (k > dp[x][y+1]){
                    k -= dp[x][y+1];
                    x++;
                    ans += 'V';
                }
                else{
                    y++;
                    ans += 'H';
                }
            }
        }
        return ans;
    }
};