Easy understandable DP Solution | C++ | O(n*m)
\nint n,m;\nint cache[20][20];\nstring res;\nint dp(int x,int y){\n    int &ans = cache[x][y];\n    if(x > n or y > m)\n        return ans = 0;\n    if(x == n a
```\nint n,m;\nint cache[20][20];\nstring res;\nint dp(int x,int y){\n    int &ans = cache[x][y];\n    if(x > n or y > m)\n        return ans = 0;\n    if(x == n and y == m)\n        return ans = 1;\n    if(ans != -1)\n        return ans;\n    ans = dp(x,y+1) + dp(x+1,y); \n    return ans;\n}\nvoid dp1(int x,int y,int k)\n{\n    if(x > n or y > m)\n        return;\n    if(x == n and y == m)\n        return;\n    int &ans = cache[x][y];\n    int l = cache[x][y+1];\n    if(l >= k){\n        res += \'H\';\n        dp1(x,y+1,k);\n        return;\n    }\n    res += \'V\';\n    dp1(x+1,y,k-l);\n}\n\nclass Solution {\npublic:\n    string kthSmallestPath(vector<int>& d, int k) {\n        n = d[0];\n        m = d[1];\n        memset(cache,-1,sizeof(cache));\n        dp(0,0);\n        res = "";\n        dp1(0,0,k);\n\n        return res;\n    }\n};\n```\n\n![image](https://assets.leetcode.com/users/images/17c1bd4c-5eaa-4b5e-b9c8-4f356767daa9_1604311353.9740295.png)\n\n```\n# Destinaton = [1,2]\n\n# If you oberved carefully how to filled *cache* table then you can see that the imediate left node of root_node(0,0) contain value 2 that indicate  from that pos(0,1) we have 2 valid way to reach  destination_node(1,2) and lexicographical order of those instruction will be 1 and 2.\n\n# The imediate right node of root_node(0,0) contain value 1 that indicate  from that pos(1,0) we have 1 valid way to reach  destination_node(1,2) and lexicographical order of this instruction will be 3(as already 2 valid instruction found in left node which lexicographically smaller than this instruction).\n\n# l >= k means kth lexicographically smallest instruction must be present in left subtree of that node so we need to move right or horizontally and append \'H\' to the res\n# Otherwise we move right subtree of that node (i.e actually move vertically or down from that position) and append \'V\' to the res. \n# when we move right subtree we decrease the value of k by l because we already found l number of instruction in left subtree which lexicograpically smaller then any instruction of right subtree.\n# So we need to actually find (k-l)th smallest instruction in right subtree.\n\n# lets take an example row   = 1 and col = 2 and k = 2, so we passes dp1(x = 0, y = 0, k = 2) from main.\n# 1st, l = cache[0][1] = 2 as l >= k we move left subtree i.e. dp1(0,1,2) and res = \'H\'.\n# 2nd, l = cache[0][2] = 1 as l < k so we move right subtree i.e. dp1(1,1,1) and res = "HV"\n# 3rd, l = cache[1][2] = 1 as l >= k so we move left subtree i.e. dp1(1,2,1) and res = "HVH"\n# 4th, as x = row and y = col so simple return and resultant instruction will be "HVH".\n\n\n\n\n```\n
['Dynamic Programming', 'C']