[Python 3] easy DP O(m * n) solution, explained
First, we build DP array to compute number of unique paths from grid[i][j] to destination grid[-1][-1].\n\nApparently, dp[i][j] = dp[i][j + 1] + dp[i + 1][j], t
* First, we build DP array to compute number of unique paths from ```grid[i][j]``` to destination ```grid[-1][-1]```.\n![image](https://assets.leetcode.com/users/images/a135e9aa-8f74-4cc8-99c3-5b95ae7a5073_1614626616.2132363.png)\nApparently, dp[i][j] = dp[i][j + 1] + dp[i + 1][j], the number of path in the current grid is equal to the number of which in the next right grid, and in the next bottom grid.\nSo the question is like to find the k-th path from ```dp[0][0]``` to ```dp[m][n]```, in the lexicographical order.\n\n* Next, start from top-left corner of ```dp```, we have two choices: go to the next right grid, or go to the next bottom grid. The key is **Every path in the next bottom grid is larger every path in the next right grid**, because **every path in the next right bottom start with "H", while paths in the next bottom grid start with "V"**. \n\nTherefore:\n1.  If the current index ```k``` is no larger than the number of paths in the right grid ( ```dp[i][j + 1]```), we will go to the next right grid, and add "H" to the answer, because we are moving rightward.\n\n2.  If the current index ```k``` is larger than ```dp[i][j + 1]```, meanning we can only find the path downward, so we will go to dp[i + 1][j], and k -= dp[i][j + 1], since we have passed the first dp[i][j + 1]-th paths, and add "V" to the ans since we are moving downward.\n\n![image](https://assets.leetcode.com/users/images/e935cd7f-1473-4aa5-97f0-e8014343a887_1614627227.0005882.png)\n\n\n* Until we reach ```i == m or j == n```, meaning we can only go rightward or downward from then on, so we just need to add numbers of "H" or "V" accordingly.\n\n\n\n\n```\ndef kthSmallestPath(self, destination: List[int], k: int) -> str:\n        m, n = destination\n        dp = [[0] * (n + 1) for _ in range(m + 1)]\n        for i in range(n):\n            dp[-1][i] = 1\n        for i in range(m):\n            dp[i][-1] = 1\n        for i in range(m - 1, -1, -1):\n            for j in range(n - 1, -1, -1):\n                dp[i][j] = dp[i + 1][j] + dp[i][j + 1]\n                \n        ans, i , j = "", 0, 0\n        while i < m and j < n:\n            if k > dp[i][j + 1]:\n                k -= dp[i][j + 1]\n                i += 1\n                ans += "V"\n            else:\n                j += 1\n                ans += "H"\n        ans += (n - j) * "H" + (m - i) * "V"  \n        return ans\n```
[]