Observational DP
Intuition\n Describe your first thoughts on how to solve this problem. \nU should observe that optimal answer is strictly decreasing sequence\n# Approach\n Desc
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nU should observe that optimal answer is strictly decreasing sequence\n# Approach\n<!-- Describe your approach to solving the problem. -->\nwe will fact that "optimal answer is strictly decreasing sequence"\nto optimise dp[mask showing previous used rows][last maximum choosen]\n# Complexity\n- Time complexity:$$O(100*n*logm*2^n+n*m*logm)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(100*2^n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n\n        // Sort each row in increasing order\n        for (int i = 0; i < n; ++i) {\n            sort(grid[i].begin(), grid[i].end());\n        }\n        \n        vector<vector<int>> dp(1 << n, vector<int>(102, 0));\n\n        // Initializebase case\n        for (int j = 0; j < 102; ++j) {\n            dp[(1<<n)-1][j] = 0;\n        }\n\n        for (int i = (1 << n) - 2; i >= 0; --i) {\n            for (int j = 0; j <= 101; ++j) {\n                dp[i][j]=0;\n                for (int c = 0; c < n; ++c) {\n                    if (!(i & (1 << c))) {\n                        // Find the largest value in row c that is less than j\n                        auto it = lower_bound(grid[c].begin(), grid[c].end(), j);\n                        if (it != grid[c].begin()) {\n                            int value = *(--it);\n                            dp[i][j] = max(dp[i][j], value + dp[i | (1 << c)][value]);\n                        }\n                    }\n                }\n            }\n        }\n        \n        return dp[0][101];\n    }\n};\n\n```
['Binary Search', 'Dynamic Programming', 'Sorting', 'Bitmask', 'C++']