[Golang] O(m*n) solution with picture explain, end->start then start->end
First we calculate how many paths from any point to end point, using f(i, j) = f(i+1, j) + f(i, j+1).\n\n\nThen we can walk from start point to end point, say w
First we calculate how many paths from any point to end point, using f(i, j) = f(i+1, j) + f(i, j+1).\n![image](https://assets.leetcode.com/users/images/44cb68ae-1586-4c43-9504-9e7b4133e027_1604299930.3191037.png)\n\nThen we can walk from start point to end point, say we want kth path where k=3.\nNow we know from (0, 1) to end point there are 6 paths, and from (1, 0) to end point there are 4 paths.\n![image](https://assets.leetcode.com/users/images/7737b68a-ea31-4582-aeb3-a56f5f4b40a1_1604300198.8034694.png)\n\nNo matter what the suffix is, the 6 paths from (0, 1) must be:\nHxxxx\nHxxxx\nHxxxx\nHxxxx\nHxxxx\nHxxxx\nand the 4 paths from (1, 0) must be:\nVxxxx\nVxxxx\nVxxxx\nVxxxx\n\nSo it is certain that any path in the 6 paths from (0, 1) **must be smaller than** any path in the 4 paths from (1, 0), so the 3rd path must in (0, 1).\nAnd if k=7, the 7th path must in (1, 0).\n\nRepeat this until we reach the end point.\n\n```go\nfunc kthSmallestPath(destination []int, k int) string {\n    row, col := destination[0], destination[1]\n    f := make([][]int, row+2)\n    for i := 0; i <= row+1; i++ {\n        f[i] = make([]int, col+2)\n    }\n    f[row][col] = 1\n    for i := row; i >= 0; i-- {\n        for j := col; j >= 0; j-- {\n            if i == row && j == col {\n                continue\n            }\n            f[i][j] = f[i+1][j] + f[i][j+1]\n        }\n    }\n    result := ""\n    i, j := 0, 0\n    for {\n        if i == row {\n            j++\n            result = result + "H"\n        } else if j == col {\n            i++\n            result = result + "V"\n        } else {\n            if k <= f[i][j+1] {\n                j++\n                result = result + "H"\n            } else {\n                k -= f[i][j+1]\n                i++\n                result = result + "V"\n            }\n        }\n        if i == row && j == col {\n            break\n        }\n    }\n    \n    return result\n}\n```
['Dynamic Programming', 'Go']