Python 3 || Bottom up dp solution | Very fast, beats 99%
\n\n## Intuition\nJust need to precompute the combinations in the dp array. Then, at every step, choose to go right if the rest of matrix has more paths than k.
![image.png](https://assets.leetcode.com/users/images/2cd9fc53-bea6-4953-9364-47fa3433439d_1724417182.9603717.png)\n\n## Intuition\nJust need to precompute the combinations in the dp array. Then, at every step, choose to go right if the rest of matrix has more paths than k. Choose to go down otherwise.\n\n## Complexity\n`m = destination[0] + 1`\n`n = destination[1] + 1`\n- Time complexity:\n$O(m \\times n)$ to make dp array\n$O(m + n)$ in the worst case for dp array traversal\nSo, $O(m \\times n)$\n\n- Space complexity:\n$O(m \\times n)$ for dp array\n\n## Code\n```python3 []\nclass Solution:\n    \n    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n        m, n = destination\n        # dp[i][j] means how many paths are there from cell (i, j) to the right bottom cell (m, n).\n        dp = [[1] * (n + 1) for _ in range(m + 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 = \'\'\n        # starting from top left cell\n        i, j = 0, 0\n        while k > 1:\n            if dp[i][j + 1] < k:\n                # using \'H\'-move will not give enough paths\n                ans += \'V\'\n                k -= dp[i][j + 1]\n                # k is the number of paths still needed once we use all paths using \'H\'-move\n                i += 1\n            else:\n                # using \'H\' move is good to have at least k paths.\n                j += 1\n                ans += \'H\'\n        \n        # we want to close the path with the first path from cell (i, j) to cell (m, n)\n        ans += \'H\' * (n - j) + \'V\' * (m - i)\n        \n        return ans\n        \n```
['Dynamic Programming', 'Python3']