solution explained [recursion -> bitmask DP  -> greedy + bitmasking]
Recursion \n\n#### approach \n\nWe will start by picking each element one by one from every row to see what is the maximum score we can get from all the combina
## Recursion \n\n#### approach \n\nWe will start by picking each element one by one from every row to see what is the maximum score we can get from all the combinations.\n\nNote: `We can even decide not to choose any number from a row.`\n\nfor ex : \n[5 , 5]\n[5, 5]\n[10, 1]\n\nIn the above case, we will not pick any number from the second row (otherwise, it will violate the second condition).\n\n```\nclass Solution {\npublic:\n    int max_score ( vector<vector<int>> & ar, int i, unordered_map<int, int> &mp){\n        int n = ar.size();\n        if(i == n)\n            return 0;\n        int res = 0;\n        for(auto x : ar[i])\n            if(!mp[x]){\n\t\t\t    // set mp[x] =1 , to not pick this number again for other rows.\n                mp[x] = 1;\n                res = max(res, max_score(ar, i + 1, mp) + x);\n\t\t\t\t// set mp[x] =0 , to make it pickable again.\n                mp[x] = 0;\n            }\n\t\t// Skip picking number from this row\n        res = max(res, max_score(ar, i + 1, mp));\n        return res;\n            \n    }\n    int maxScore(vector<vector<int>>& ar) {\n\t   // map to keep track of which number i have included \n        unordered_map<int, int> mp;\n        return max_score(ar, 0, mp);\n    }\n};\n```\n\nTime complexity : `O ( N  ^ N) )` , where N = size of the grid \nSpace complexity : `O ( N * N ) ` , where N = size of the grid , Why? Because this is the maximum number we can have which we will be storing in the map.\n\n\n## Adding greedy optimisation : \n\nNow, here are some observations we can use to optimize our above approach a little bit.\n\n1. `we can even decide to not choose any number from the row` -> We will only do this when we can\'t pick any element from that row; otherwise, it\'s always better to pick some number as they are greater than 0.\n2. It\'s better to always pick the largest number.\n\nBut the problem here is that it could be repeating in some other row, and picking it now may result in a lesser max score.\n\nfor ex. \n[\n[8,7,6],\n[8,3,2]\n]\n\nIt\'s a better choice to not pick 8 in the first row, as we then won\'t be able to pick 8 again in the second row.\n\nBUT what if the largest number is not repeating in any other row? Then it always makes sense to pick it.\n\n```\nclass Solution {\npublic:\n    int max_score ( vector<vector<int>> & ar, int i, unordered_map<int, int> &mp, vector<unordered_map<int, int> > &mp2){\n        int n = ar.size();\n        if(i == n)\n            return 0;\n        int res = 0;\n        bool cant_pick_number_from_row = true;\n        for(auto x : ar[i]){\n            int definately_pick = 0;\n            // checking x occurrence in other rows.\n            for (int j = 0 ; j < n; j ++){\n                // leave the current row.\n                if(i != j){\n                    definately_pick += mp2[j][x];\n                }\n            }\n            \n            if(!mp[x]){\n\t\t\t    // set mp[x] =1 , to not pick this number again for other rows.\n                mp[x] = 1;\n                cant_pick_number_from_row = false;\n                res = max(res, max_score(ar, i + 1, mp, mp2) + x);\n\t\t\t\t// set mp[x] =0 , to make it pickable again.\n                mp[x] = 0;\n                if(!definately_pick){\n                // if it\'s not occurring in other rows , then there is no need to check for lesser number as they we always give less total score. \n                    break;\n                }\n                \n            }\n        }\n\t\t// Skip picking number from this row, only if we can not pick any number from this row.\n        if(cant_pick_number_from_row)\n            res = max(res, max_score(ar, i + 1, mp, mp2));\n        return res;\n            \n    }\n    int maxScore(vector<vector<int>>& ar) {\n\t   // map to keep track of which number i have included \n        unordered_map<int, int> mp;\n        \n        // Map to keep track of the number in every row, we will use to to check if we can\n        // "DEFINITELY" pick the largest possible number\n        vector<unordered_map<int, int> > mp2(ar.size());\n        \n        for(int i = 0; i < ar.size(); i++){\n            //  Sorting the array in descending order so that i can choice large number first.         \n            sort(ar[i].begin(), ar[i].end(), greater<>() );\n            for(int x : ar[i])\n                mp2[i][x]++;\n        }\n        \n        \n        return max_score(ar, 0, mp, mp2);\n    }\n};\n```\n\nTime complexity : although we improve it a little but i think it\'s complexity in the wrost case is still O(N ^N ).\nspace complexity : O ( N ^ N )\n\nNOTE : This will still give TLE. So why do this? Because in DP bitmasking, I was using a string instead of an integer, which was also giving TLE, but after adding the above optimizations, it got passed.\n\n\n\n\n\n## DP with bitmask : \n\n`what is bitmask DP`\n\nIn normal DP, our result memorization depends on some value. For example, how many steps until we reach the top ( [problem link](https://leetcode.com/problems/climbing-stairs/) ), which house we are robbing, and whether we robbed the previous house or not ( [problem link](https://leetcode.com/problems/house-robber-ii/) ). \n\nBut in some questions, our memorization depends on some combinations. Like in this question, to decide whether we have computed the answer already, we need to know at what row we are (`i`) and what were the numbers we have chosen previously (`mp`). If we can somehow use the store and return the result based on i & mp, then we will reduce our repetitive computations. \n\n\nTo store combinations, we use bitmasking. (You don\'t need to know more; I\'m sure once you go through the code, you will understand it. Plus, I can\'t tell you more about it in this article. Just do 2-3 questions on bitmask DP to get more familiar with it.)\n\n[DP question list](https://leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months)\n\nNow to store the number I have picked, I will change mp from unordered_map to string, so that I can easily store it in `unordered_map<int, unordered_map<string, int>> dp;`\n\n```\nclass Solution {\npublic:\n    int max_score ( vector<vector<int>> & ar, int i, string & mp, vector<unordered_map<int, int> > & mp2, unordered_map<int, unordered_map<string, int>> &dp )\n    {\n        int n = ar.size();\n        if(i == n)\n            return 0;\n        if(dp[i][mp])\n            //  why re-compute when we already know the answer.           \n            return dp[i][mp];\n\n        int res = 0;\n        bool cant_pick_number_from_row = true;\n        for(auto x : ar[i]){\n            int definately_pick = 0;\n            // checking x occurrence in other rows.\n            for (int j = 0 ; j < n; j ++){\n                // leave the current row.\n                if(i != j){\n                    definately_pick += mp2[j][x];\n                }\n            }\n            \n            if(mp[x] == \'0\'){\n\t\t\t    // set mp[x] =1 , to not pick this number again for other rows.\n                mp[x] = \'1\';\n                cant_pick_number_from_row = false;\n                res = max(res, max_score(ar, i + 1, mp, mp2, dp) + x);\n\t\t\t\t// set mp[x] =0 , to make it pickable again.\n                mp[x] = \'0\';\n                if(!definately_pick){\n                // if it\'s not occurring in other rows , then there is no need to check for lesser number as they we always give less total score. \n                    break;\n                }\n                \n            }\n        }\n\t\t// Skip picking number from this row, only if we can not pick any number from this row.\n        if(cant_pick_number_from_row)\n            res = max(res, max_score(ar, i + 1, mp, mp2, dp));\n        \n        // store to result to avoid repeatative computation.\n        return dp[i][mp] = res;\n            \n    }\n    int maxScore(vector<vector<int>>& ar) {\n\t   // map to keep track of which number i have included \n        int MAX_ELEMENT_LIMIT = 100;\n        string mp(MAX_ELEMENT_LIMIT + 1, \'0\');\n        \n        // Map to keep track of the number in every row, we will use to to check if we can\n        // "DEFINITELY" pick the largest possible number\n        vector<unordered_map<int, int> > mp2(ar.size());\n        \n        for(int i = 0; i < ar.size(); i++){\n            // Sorting the array in descending order so that i can choice large number first.         \n            sort(ar[i].begin(), ar[i].end(), greater<>() );\n            for(int x : ar[i])\n                mp2[i][x]++;\n        }\n        \n        unordered_map<int, unordered_map<string, int>> dp;\n        \n        \n        return max_score(ar, 0, mp, mp2, dp);\n    }\n};\n```\n\n\nTime complexity : i think O ( N * S), where N = no of grids, S = number range.\nSpace : O( N * S ) \n\nplease correct me if i\'m wrong ^. \n\n\nmy journey : \n\nI first coded a recursive approach, then bitmask DP, but it was still giving TLE (maybe because I used a string instead of an integer for bitmask, but I was not sure how to do that). So, I added a greedy optimization, and it got passed.\n\nPlease comment if you have any doubts/questions or want to correct something.\n\n\n
['Greedy', 'Recursion', 'C', 'C++']