[Java/C++] Top Down DP | Memoisation
Note :\nRefer the post below for understanding why we should modulo in the end only.\nhttps://leetcode.com/problems/get-the-maximum-score/solutions/769334/c-sol
## Note :\nRefer the post below for understanding why we should modulo in the end only.\nhttps://leetcode.com/problems/get-the-maximum-score/solutions/769334/c-soln-reason-behind-modulo-in-the-end-and-not-at-every-step/ \nThank you [@pranjal21gupta](https://leetcode.com/pranjal21gupta/)\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    int n1, n2;\n    unordered_map<int,int> idx1, idx2;\n    vector<vector<long long>> dp;\n    long long helper(vector<int>& nums1, vector<int>& nums2, int curr, int type) {\n        if (((type == 0) and (curr >= n1)) or ((type == 1) and (curr >= n2)))\n            return 0;\n        if (dp[curr][type] != -1)   \n            return dp[curr][type];\n        \n        long long res = 0;\n        res = fmax(res, \n            ((type == 0) ? nums1[curr] : nums2[curr]) + \n            helper(nums1, nums2, curr + 1, type));\n\n        if (((type == 0) and idx2.count(nums1[curr])) or ((type == 1) and idx1.count(nums2[curr]))) \n            res = fmax(res, \n                ((type == 0) ? nums1[curr] : nums2[curr]) + \n                helper(nums1, nums2, ((type == 0) ? idx2[nums1[curr]] : idx1[nums2[curr]]) + 1, 1 - type));\n        return dp[curr][type] = res;\n    }\n\n    int maxSum(vector<int>& nums1, vector<int>& nums2) {\n        n1 = nums1.size();\n        n2 = nums2.size();\n\n        for (int i = 0; i < n1; i++)\n            idx1[nums1[i]] = i;\n        for (int i = 0; i < n2; i++)\n            idx2[nums2[i]] = i;\n    \n        dp.resize(max(n1,n2), vector<long long> (2, -1));\n        long long ans = fmax(\n            helper(nums1,nums2, 0, 0),\n            helper(nums1,nums2, 0, 1)\n        );\n        return ans % mod;\n    }\n};\n```\n```Java []\nclass Solution {\n    final int mod = 1000000007;\n    int n1, n2;\n    Map<Integer, Integer> idx1, idx2;\n    long[][] dp;\n\n    long helper(int[] nums1, int[] nums2, int curr, int type) {\n        if (((type == 0) && (curr >= n1)) || ((type == 1) && (curr >= n2)))\n            return 0;\n        if (dp[curr][type] != -1)\n            return dp[curr][type];\n\n        long res = 0;\n        res = Math.max(res,\n                ((type == 0) ? nums1[curr] : nums2[curr]) +\n                        helper(nums1, nums2, curr + 1, type));\n\n        if (((type == 0) && idx2.containsKey(nums1[curr])) || ((type == 1) && idx1.containsKey(nums2[curr])))\n            res = Math.max(res,\n                    ((type == 0) ? nums1[curr] : nums2[curr]) +\n                            helper(nums1, nums2, ((type == 0) ? idx2.get(nums1[curr]) : idx1.get(nums2[curr])) + 1, 1 - type));\n\n        return dp[curr][type] = res;\n    }\n\n    public int maxSum(int[] nums1, int[] nums2) {\n        n1 = nums1.length;\n        n2 = nums2.length;\n\n        idx1 = new HashMap<>();\n        idx2 = new HashMap<>();\n\n        for (int i = 0; i < n1; i++)\n            idx1.put(nums1[i], i);\n        for (int i = 0; i < n2; i++)\n            idx2.put(nums2[i], i);\n\n        dp = new long[Math.max(n1, n2)][2];\n        for (int i = 0; i < Math.max(n1, n2); i++) {\n            Arrays.fill(dp[i], -1);\n        }\n\n        long ans = Math.max(\n                helper(nums1, nums2, 0, 0),\n                helper(nums1, nums2, 0, 1)\n        );\n        return (int) (ans % mod);\n    }\n}\n```
['C++']