Easy Combinatorics
Intuition\n Describe your first thoughts on how to solve this problem. \nbinomialCoefficient function: Computes C(n,k) efficiently using dynamic programming.\nk
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nbinomialCoefficient function: Computes C(n,k) efficiently using dynamic programming.\nkthSmallestPath function:\nAt each step, we decide whether to place an \'H\' or \'V\' by calculating how many paths would start with \'H\'. If placing an \'H\' would skip fewer than k paths, we place \'H\'. Otherwise, we place \'V\' and adjust k.\nContinue this process until the entire path is built.\nMain Function: Takes the input destination and the value of k, and outputs the k-th smallest path.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O((row+col)^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n// Function to calculate binomial coefficient C(n, k)\nint binomialCoff(int n, int k) {\n    if (k > n) return 0;\n    if (k == 0 || k == n) return 1;\n    \n    vector<int> C(k + 1, 0);\n    C[0] = 1; // C(n, 0) is 1\n\n    for (int i = 1; i <= n; i++) {\n        for (int j = min(i, k); j > 0; j--) {\n            C[j] = C[j] + C[j - 1];\n        }\n    }\n    \n    return C[k];\n}\n    string kthSmallestPath(vector<int>& d, int k) {\n        int y=d[0],x=d[1];\n        string ans="";\n        while(y>0 && x>0){\n            // Calculate the number of paths if we choose \'H\' first\n            int H=binomialCoff(x+y-1,y);\n            if(k<=H){\n                ans+="H";\n                x--;\n\n            }\n            else{\n                ans+="V";\n                y--;\n                k-=H;\n            }\n\n        }\n        \n        while(x){\n            ans+="H";\n            x--;\n        }\n        while(y) {\n            ans+="V";\n            y--;\n        }\n       \n        return ans;\n        \n    }\n};\n```
['C++']