Java simple solution using DFS and memoization beats 83%
The idea is to first write a method to do dfs (with memoization) to find number of ways to reach destination from coordinates x and y.  This is the key step to 
The idea is to first write a method to do dfs (with memoization) to find number of ways to reach destination from coordinates `x` and `y`.  This is the key step to the solution.\nOnce we have done that then we can realize that\n\n- `dfs(dest, x, y) == dfs(dest, x, y+1) + dfs(dest, x+1, y)`.  This is because these are only two ways to reach the destination. Let\'s call these search spaces `hSpace` and `vSpace` respectively. \n- the `hSpace` is lexicographically smaller than `vSpace`.\n- If `k <= dfs(dest, x, y+1)` then we know the search space starts with an "H", and we can continue in `hSpace`. Like say total ways to reach destination are 1000, of which 900 are in `hSpace` and 100 in `vSpace`. Now if we are looking for 200th entry then we know that we need to start with an "H", and look for 200 in the `hSpace`. \n- If `k > dfs(dest, x, y+1)` then we know search space starts with a "V", and we are looking for `(k - dfs(dest, x, y+1)` entry in this search space space. Like say total ways to reach destination are 1000, of which 900 are in `hSpace` and 100 in `vSpace`. Now if we are looking for 950th entry then we know that we need to start with a "V", and look for (950-900 == 50th) position in the `vSpace`. \n- We add an "H", or a "V" based on which track we followed in the last step(s).\n- We continue updating our `x`,` y` and `k` in a loop\n- We continue doing this till we reach our destination\n\n```\nclass Solution {\n    Integer[][] cache = null;\n    public String kthSmallestPath(int[] destination, int k) {\n        cache = new Integer[destination[0]+1][destination[1]+1];\n        StringBuffer sb = new StringBuffer();\n        int x = 0, y = 0;\n        while (true) {\n            if (x == destination[0] && y == destination[1]) break;\n            int h = (y < destination[1]) ? dfs(destination, x, y+1) : 0;\n            int v = (x < destination[0]) ? dfs(destination, x+1, y) : 0;\n            \n            if (k <= h) {\n                sb.append("H");\n                y += 1;\n            } else {\n                sb.append("V");\n                k = k-h;\n                x += 1;\n            }\n        }\n        return sb.toString(); \n    }\n    \n    int dfs(int[] dest, int x, int y) {\n        if (cache[x][y] != null) return cache[x][y];\n        if (x == dest[0] && y == dest[1])  return 1;\n        \n        int tot = 0;\n        if (y+1 <= dest[1])\n            tot += dfs(dest, x, y+1);\n        \n        if (x+1 <= dest[0])\n            tot += dfs(dest, x+1, y);\n        \n        cache[x][y] = tot;\n        return tot;\n    }\n}\n```
[]