Recursive DP solution with intuition
Intuition\n Describe your first thoughts on how to solve this problem. \nThe actual complication in the problem is in deciding which array should we sort.\nTo h
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe actual complication in the problem is in deciding which array should we sort.\nTo help this simplify, understand that elements in nums1 contribute only once to every index while nums2 contribute at every second.\neg. nums1: [500, 100], nums2: [1, 100]\nAt t=1, [501, 200]\nAt t=2, [502, 300]\nAt t=3, [503, 400]\nAt t=4, [504, 500]\nAt t=5, [505, 600]\n\nFrom above example you see, although the value at index 0 for nums1 was greater but with time value at index 1 overtook it. So sorting should be done based on the values present in nums2.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the array based on num2\nApply recursive dp solution for finding answer for each time from t=1 to n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2), as we are calculating the value of 2d array\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n# Code\n```\nclass Solution {\n\n    int dp[][];\n    boolean vis[][];\n\n    int solve(List<Integer> nums1, List<Integer> nums2, ArrayList<Integer> indexAl, int curTime, int curIndex) {\n        int n = nums1.size();\n\n        if (curIndex >= n || curTime <= 0) {\n            return 0;\n        }\n\n        if (vis[curIndex][curTime]) {\n            return dp[curIndex][curTime];\n        }\n\n        int actualIndex = indexAl.get(curIndex);\n\n        int ans = 0;\n\n        // first option, can skip making it zero\n        ans = nums1.get(actualIndex) + nums2.get(actualIndex) * (curTime)\n                + solve(nums1, nums2, indexAl, curTime - 1, curIndex + 1);\n\n        ans = Math.max(ans, solve(nums1, nums2, indexAl, curTime, curIndex + 1));\n\n        vis[curIndex][curTime] = true;\n        dp[curIndex][curTime] = ans;\n\n        return ans;\n    }\n\n    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int target) {\n        int ans = -1;\n        int n = nums1.size();\n\n        ArrayList<Integer> indexAl = new ArrayList<>();\n\n        int sumNums1 = 0;\n        int sumNums2 = 0;\n\n        for (int i = 0; i < n; i++) {\n            indexAl.add(i);\n\n            sumNums1 = sumNums1 + nums1.get(i);\n            sumNums2 = sumNums2 + nums2.get(i);\n        }\n\n        if (sumNums1 <= target) {\n            return 0;\n        }\n\n        Collections.sort(indexAl, (a, b) -> {\n            return nums2.get(b) - nums2.get(a);\n        });\n\n        dp = new int[n + 1][n + 1];\n        vis = new boolean[n + 1][n + 1];\n\n        for (int i = 1; i <= n; i++) {\n            solve(nums1, nums2, indexAl, i, 0);\n\n            if (sumNums1 + sumNums2 * i - dp[0][i] <= target) {\n                ans = i;\n                break;\n            }\n        }\n\n        return ans;\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Java']