simple cpp dp (m x n)
First let\'s calculate and save how many ways we can arrive to destination starting from i, j.\nFor example for [2, 3] k = 1\nour dp will look like\n10 6  3  1 
First let\'s calculate and save how many ways we can arrive to destination starting from i, j.\nFor example for [2, 3] k = 1\nour dp will look like\n10 6  3  1 \n 4  3  2  1 \n 1  1  1  1 \n starting from 0,0 if ```dp[i][j] >= k``` we will go to right until `dp[i][j] < k` then we go down.\n```\nclass Solution {\npublic:\n    string kthSmallestPath(vector<int>& d, int k) {\n        int n = d[0], m = d[1];\n        string res;\n        vector<vector<int>> dp(n + 1, vector<int> (m + 1, 1));\n        \n        for (int i = n - 1; i >= 0; i--)\n            for (int j = m - 1; j >= 0; j--)\n                dp[i][j] = dp[i][j + 1] + dp[i + 1][j];\n\n        for (int j = 0, i = 0; j < m || i < n;) {\n            if (dp[i][j] >= k && j < m) {\n                res.push_back(\'H\');\n                j++;\n            }\n            else {\n                if ((k -= dp[i][j]) > 0) // else we are on the final column so we dont have to decrement value of j\n                    j--, res.pop_back();\n                res.push_back(\'V\');\n                i++;\n            }\n        }\n        return res;\n    }\n};\n```\nEdit \nI started with brute force `dfs` at the beginning (Not knowing `k` can go to a very high number).  Then I realized that we don\'t have to generate all those combinations. So I decided to start from the destination save how many ways we can reach to destination from [i, j]. So we will avoid `k - 1` ways and looking for `k`th route.
['Dynamic Programming', 'C']