✅combinatorics || DP || cPP
Intuition\nTo find the k-th smallest path from the top-left corner to a destination in a grid, we need to account for all possible paths and determine which pat
# Intuition\nTo find the k-th smallest path from the top-left corner to a destination in a grid, we need to account for all possible paths and determine which path falls in the k-th position lexicographically. The idea is to use dynamic programming to count the number of paths from each point to the destination, allowing us to determine the direction of the k-th path step by step.\n\n# Approach\n- Dynamic Programming Table: Construct a 2D table arr where arr[i][j] represents the number of paths from point (i, j) to the destination. Initialize the destination cell with 1 because there\'s exactly one way to be at the destination.\n- Fill the DP Table: Iterate from the bottom-right to the top-left of the grid, filling each cell based on the number of ways to reach the destination from the cells directly below and to the right.\n- Construct the k-th Path: Starting from the top-left corner, decide whether to move horizontally (right) or vertically (down) by checking the number of paths from the next possible positions. Use this information to build the k-th path by reducing k accordingly when moving down.\n\n\n# Code\n```\nclass Solution {\npublic:\n    string kthSmallestPath(vector<int>& destination, int k) {\n        int r=destination[0]+1;\n        int c=destination[1]+1;\n        vector<vector<long long>>arr(r,vector<long long>(c,0));\n        arr[r-1][c-1]=1;\n        for(int i=r-1;i>=0;i--){\n            for(int j=c-1;j>=0;j--){\n                if(i==r-1 && j==c-1)arr[i][j]=1;\n                else if(i==r-1)arr[i][j]=arr[i][j+1];\n                else if(j==c-1)arr[i][j]=arr[i+1][j];\n                else arr[i][j]=arr[i+1][j]+arr[i][j+1];\n            }\n        }\n        string ans="";\n        int i=0,j=0;\n        // cout<<r<<c<<endl;\n        while(ans.length()!=r+c-2){\n            // cout<<i<<" "<<j<<" "<<ans<<endl;\n            if(j+1<c && arr[i][j+1]<k){\n                ans+="V";\n                k-=arr[i][j+1];\n                i++;\n            }\n            else if(j+1<c){\n                ans+="H";\n                j++;\n            }\n            else{\n                ans+="V";\n                i++;\n            }\n        }\n        return ans;\n    }\n};\n```
['Array', 'Math', 'Dynamic Programming', 'Combinatorics', 'C++']