[Python/Java] Walking through example with DP approach, builds on LC #62. Unique Paths
I recommend solving unique-paths first (with a bottom-up dp approach). We will use it to create the dp table.\n\nSpecifically, we will build a dp table where $d
I recommend solving [unique-paths](https://leetcode.com/problems/unique-paths/) first (with a bottom-up dp approach). We will use it to create the dp table.\n\nSpecifically, we will build a dp table where $dp[i][j]$ denotes the number of unique paths to reach the bottom-right corner, starting from indexes i, j\n\nFor example, \ndestination = [2, 3], k = 3\nwill have the following dp table:\n```\n10  6   3   1\n\n4   3   2   1 \n  \n1   1   1   1\n```\n<pre>\nLets look at dp[0][0],\nThere are 10 unique paths\n    if we move right, we then have 6 unique paths left\n        ["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH"]\n    if we move down, we then have 4 unique paths left\n        ["VHHHV", "VHHVH", "VHVHH", "VVHHH"]\n</pre>\n\nThe 6 paths on moving right are lexicographically smaller than the 4 paths on moving down\n\nWe want the 3rd smallest path(we are given k=3). So we choose to move right since the 3rd smallest path will be amongst the 6 smallest paths.\n\n```\n10__6   3   1\n    ^    \n4   3   2   1 \n  \n1   1   1   1\n```\nWe are now at dp[0][1] = 6, moving right will mean our path will be amongst the 3 smallest paths, so we move right.\n```\n10__6___3   1\n        ^\n4   3   2   1 \n  \n1   1   1   1\n```\nWe are now at dp[0][2] = 3, we don\'t want to move right since then our path will be amongst the 1 smallest path(s), so we don\'t do that(since k = 3, we want the 3rd smallest path).\nWe move down instead.\n\nThere is one thing to note when moving down. \nAgain, all the paths when moving right are lexicographically smaller than all the paths when moving down.\nSo you could imagine that all the unique paths when moving down are all "shifted" in lex order by the number of paths on the right.\n\nYou could also view this as a subproblem where we are looking at the unique paths starting from indexes i, j\n\nWe can encode this into our implementation by subtracting our k value by dp[i][j+1] \nso in this case:\n```\nk := k - dp[i][j+1]\n   = k - dp[0][3]\n   = 3 - 1 # so now k is 2\n```\n\n\n```  \nk = 2\n10__6___3   1\n        |\n4   3   2   1 \n        ^\n1   1   1   1\n```\nWe are now at dp[1][2] = 2, k = 2, we don\'t want to move right since then  path will be the 1st smallest path(inside the subproblem perspective).\nSo we move down.\n\n```  \nk = 1\n10__6___3   1\n        |\n4   3   2   1 \n        |\n1   1   1   1\n        ^\n```\nWe are now at dp[2][2] = 1, k = 1\nOnce we reach the bottom row or right column, there is only one path we can choose.\n\nOur final path is:\n```  \n10__6___3   1\n        |\n4   3   2   1 \n        |\n1   1   1___1\n"HHVVH"\n```\nWhich is indeed the 3rd smallest path out of ["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"]\n\n# High-level Recap\nWe build dp table of unique paths.\nWe traverse the dp table starting at dp[0][0].\nWe compare k with dp[i][j+1] to decide whether to move right or down.\n\n# Code\n```python []\nclass Solution:\n    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n        m, n = destination[0] + 1, destination[1] + 1\n        dp = [[0] * n for i in range(m)]\n        for i in range(m): dp[i][n-1] = 1\n        for j in range(n): dp[m-1][j] = 1\n        for i in range(m-2, -1, -1):\n            for j in range(n-2, -1, -1):\n                dp[i][j] = dp[i+1][j] + dp[i][j+1]\n        # ^ this is just LC #62. Unique Paths\n\n        sb = []\n        i, j = 0, 0\n        while i < m-1 and j < n-1: \n            """ e.g dest = [2,3], k = 3\n            10  6   3   1\n            4   3   2   1   \n            1   1   1   1\n            """\n            # move right\n            if k <= dp[i][j+1]:\n                j += 1\n                sb.append(\'H\')\n            # move down\n            else:\n                k -= dp[i][j+1]\n                i += 1\n                sb.append(\'V\')\n        # if we reach the bottom row or right column, there is only one path left\n        sb.append(\'V\' * (m-1 - i) + \'H\' * (n-1 - j))\n        # print(\'\\n\'.join([\'\\t\'.join([str(cell) for cell in row]) for row in dp]))\n        return \'\'.join(sb)\n```\n```java []\nclass Solution {\n    public String kthSmallestPath(int[] destination, int k) {\n        int m = destination[0] + 1;\n        int n = destination[1] + 1;\n        int[][] dp = new int[m][n];\n        for (int i = 0; i < m; i++) dp[i][n-1] = 1; \n        for (int j = 0; j < n; j++) dp[m-1][j] = 1; \n        for (int i = m-2; i >= 0; i--) {\n            for (int j = n-2; j >= 0; j--) {\n                dp[i][j] = dp[i+1][j] + dp[i][j+1];\n            }\n        } // ^ this is just LC #62. Unique Paths\n\n        int i = 0;\n        int j = 0;\n        StringBuilder sb = new StringBuilder();\n        while (i < m-1 && j < n-1) {\n            // e.g dest = [2,3], k = 3\n            //    10  6   3   1\n            //    4   3   2   1   \n            //    1   1   1   1\n\n            // move right\n            if (k <= dp[i][j+1]) {\n                j++;\n                sb.append(\'H\');\n            } \n            // move down\n            else {\n                k -= dp[i][j+1];\n                i++;\n                sb.append(\'V\');\n            }\n        }\n        // if we reach the bottom row or right column, there is only one path left\n        for (; i < m-1; i++) sb.append(\'V\');\n        for (; j < n-1; j++) sb.append(\'H\');\n        //System.out.println(Arrays.deepToString(dp).replace("], ", "]\\n"));\n        return sb.toString();\n    }\n}\n```\n
['Java', 'Python3']