Easy Explaination | Dynamic Programming | Beats 100%
IntuitionThe problem revolves around finding the k-th smallest lexicographical path in a grid. My intuition is to use a dynamic programming approach to count th
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem revolves around finding the k-th smallest lexicographical path in a grid. My intuition is to use a dynamic programming approach to count the number of paths at each step and leverage this information to determine the direction of movement based on k.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Use a dynamic programming (DP) table to calculate the number of paths from any cell `(i, j)` to the destination.
2. Create a helper function `h` to compute the DP table values recursively.
3. Use another recursive function `c` to construct the path by deciding whether to go right (`H`) or down (`V`) based on the value of k and the DP table.
4. Append the appropriate direction to the path string and recursively adjust k until the entire path is constructed.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
  - Computing the DP table takes $$O(m \times n)$$, where m and n are the dimensions of the grid.
  - Constructing the path takes $$O(m + n)$$ since we traverse the path once.
  - Overall time complexity: $$O(m \times n)$$.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
  - The DP table takes $$O(m \times n)$$ space.
  - The recursion stack may use $$O(m + n)$$ space in the worst case.
  - Overall space complexity: $$O(m \times n)$$.

# Code
```cpp []
class Solution {
public:
    string kthSmallestPath(vector<int>& dest, int k) {
        vector<vector<int>> dp(dest[0]+1, vector<int>(dest[1]+1, -1));
        h(0,0, dp);
        // finding path using no. of paths in a direction using dp table
        string path = "";
        return c(0,0,dp, path, k);
    }
private:
    int h(int i, int j, vector<vector<int>>& dp){
        if(i>=dp.size() || j>=dp[0].size()) return 0;
        if(i==dp.size()-1 && j==dp[0].size()-1) return dp[i][j] = 1;
        if(dp[i][j]!=-1) return dp[i][j];
        return dp[i][j] = h(i+1, j, dp) + h(i, j+1, dp);
    }
    string c(int i, int j, vector<vector<int>>&dp, string&path, int k){
        if(i==dp.size()-1 && j==dp[0].size()-1) return path;
        int right = h(i, j+1, dp);
        if(k <= right){
            path.push_back('H');
            return c(i, j+1, dp, path, k);
        }else{
            path.push_back('V');
            return c(i+1, j, dp, path, k-right);
        }
    }
};
```
['Dynamic Programming', 'C++']