C++ count dp (Explained)
Count possible routes from that point to end. Run dfs, if possible routes are less than \'K\' subtract routes from \'K\' and go back.\n\nCount matrix when desti
Count possible routes from that point to end. Run dfs, if possible routes are less than `\'K\'` subtract routes from `\'K\'` and go back.\n\nCount matrix when destination is (2,3) :-\n```\n10 6 3 1\n 4 3 2 1\n 1 1 1 1\n```\nWhat this represent is that there are 10 routes from (0, 0) , 6 routes from (0, 1) and so on.\nDuring dfs when visit a point where number of possible routes are less than required `\'K\'` routes, then we mark these route visited i.e subtract those route from `\'K\'` and go back.\nFor exmaple when `K=4` and we start moving from (0,0). At (0, 0) possible routes are 10 i.e greater than `K` so we move right. Same for (0, 1) but when we reach (0, 2) possible routes are 3 i.e less than `K` therefore there is no way we can choose `Kth` path if we continue this. Now we mark these 3 routes visited and subtract them from `K` and go back to (0, 1). At this point, we have already visited right so we will go down. This process will conitnue till we reach the end. \n```\nclass Solution {\npublic:\n    int x, y;\n    string res;\n    bool q;\n    int cnt[16][16];\n    void dfs(int i, int j, int& k, string &s){\n        if (q) return;\n        if (k>cnt[i][j]){\n            k-=cnt[i][j];\n            return;\n        }\n        if (i==x && j==y){\n                q=true;\n                res=s;\n        }\n        if (j<y){\n            s.push_back(\'H\');\n            dfs(i, j+1, k, s);\n            s.pop_back();\n        }\n        if (i<x){\n            s.push_back(\'V\');\n            dfs(i+1, j, k, s);\n            s.pop_back();\n        }\n        return;\n    }\n    \n    string kthSmallestPath(vector<int>& destination, int k) {\n        \n        x=destination[0], y=destination[1];\n        int tmp;\n        for (int i=x; i>-1; --i){\n            for (int j=y; j>-1; --j){\n                tmp=0;\n                if (i<15) tmp+=cnt[i+1][j];\n                if (j<15) tmp+=cnt[i][j+1];\n                tmp=max(1, tmp);\n                cnt[i][j]=tmp;\n            }\n        }\n        \n        \n        string s="";\n        q=false;\n        dfs(0, 0, k, s);\n        return res;\n    }\n};\n```\n
['Dynamic Programming', 'C', 'Counting']