[C++] Dynamic Programming Approach (0ms 100%) - Bottom-Up
c++\nconst int MXN = 15 + 2;\n\nclass Solution {\n    int n, m;\n\n    int dp[MXN][MXN];\n\n    int go(int x, int y) {\n        if(x==n && y==m) return 1;\n    
```c++\nconst int MXN = 15 + 2;\n\nclass Solution {\n    int n, m;\n\n    int dp[MXN][MXN];\n\n    int go(int x, int y) {\n        if(x==n && y==m) return 1;\n        if(x < 0 || x > n || y < 0 || y > m) return 0;\n        int &ans = dp[x][y];\n        if(ans != -1) return ans;\n        ans = go(x+1, y) + go(x, y+1);\n        return ans;\n    }\n    \n    string way;\n    void build(int x, int y, int k) {\n        if(x==n && y==m) return;\n        if(x < 0 || x > n || y < 0 || y > m) return;\n        if(k <= go(x, y+1)) {\n            way.push_back(\'H\');\n            build(x, y+1, k);\n        } else {\n            k -= go(x, y+1);\n            way.push_back(\'V\');\n            build(x+1, y, k);\n        }\n    }\n\npublic:\n    string kthSmallestPath(vector<int>& destination, int k) {\n        n = destination[0];\n        m = destination[1];\n        memset(dp, -1LL, sizeof(dp));\n        go(0, 0);\n        build(0, 0, k);\n        return way;\n    }\n};\n```
['Dynamic Programming', 'C']