Very Easy C# DP Solution
First pass: calculate count of all path from (row, col) to destination\nSecond pass: fill k-th trace using first pass calculations\n\n\n    public class Solutio
First pass: calculate count of all path from (row, col) to destination\nSecond pass: fill k-th trace using first pass calculations\n\n```\n    public class Solution\n    {\n        private static readonly int[][] _dirs = new[]\n        {\n            new[] {0, 1},\n            new[] {1, 0},\n        };\n\n        private int CalculateCount(int?[,] count, int n, int m, int row, int col)\n        {\n            if (count[row, col].HasValue)\n            {\n                return count[row, col].Value;\n            }\n\n            int res = 0;\n\n            foreach (var d in _dirs)\n            {\n                int newRow = row + d[0];\n                int newCol = col + d[1];\n\n                if (newRow < n && newCol < m)\n                {\n                    res += CalculateCount(count, n, m, newRow, newCol);\n                }\n            }\n\n            count[row, col] = res;\n            return res;\n        }\n\n        private void Helper(StringBuilder res, int row, int col, int?[,] counts, int k)\n        {\n            int n = counts.GetLength(0);\n            int m = counts.GetLength(1);\n\n            if (row == n - 1 && col == m - 1)\n            {\n                return;\n            }\n\n            var horRow = row + _dirs[0][0];\n            var horCol = col + _dirs[0][1];\n\n            var vertRow = row + _dirs[1][0];\n            var vertCol = col + _dirs[1][1];\n\n            if (horRow < n && horCol < m)\n            {\n                if (k < counts[horRow, horCol].Value)\n                {\n                    res.Append(\'H\');\n                    Helper(res, horRow, horCol, counts, k);\n                }\n                else\n                {\n                    res.Append(\'V\');\n                    Helper(res, vertRow, vertCol, counts, k - counts[horRow, horCol].Value);\n                }\n            }\n            else\n            {\n                res.Append(\'V\');\n                Helper(res, vertRow, vertCol, counts, k);\n            }\n        }\n\n        public string KthSmallestPath(int[] destination, int k)\n        {\n            int n = destination[0] + 1;\n            int m = destination[1] + 1;\n\n            int?[,] count = new int?[n,m];\n            count[destination[0], destination[1]] = 1;\n            CalculateCount(count, n, m, 0, 0);\n            StringBuilder res = new StringBuilder();\n            Helper(res, 0,0,count, k-1);\n            return res.ToString();\n        }\n    }\n```
['Dynamic Programming']