Recursion to Tabulation | Java
Intuition\nAfter learnings all the important conclusions that :\n- At max we will do single operation on any index\n- for any two numbers a and b from nums2, if
# Intuition\nAfter learnings all the important conclusions that :\n- At max we will do single operation on any index\n- for any two numbers a and b from nums2, if b>a then b will add more value in every second to the total sum.\nso we will opearate on index i with larger nums2[i] after we operate on all other indices with value < nums2[i]\n# Approach\n- for optimal solution we must reset any index each second\n- func(i,j) -> maximum cut that will incur to the arr[0...i] if we do j operations (obviously in j seconds)\n\nex - nums1 = [1,7,9,4,8,8,1]\n     nums2 = [2,2,3,2,0,1,0]\n     x = 20\n\nHere n = 7\n- If even after n seconds we did not get sum of array elements which is <=x then return -1\n\nsay func(i,j) will return the maximum cut incurred on [0....i] in j operations\n\n1. func(i,j-1) : this recurrence helps in calculating maximum cut in [0.....i] after all possible operations\n2. func(i-1,j-1) : if we select ith index for jth operation\n3. func(i-1,j) : we are trying to choose index for jth operation, but we did not pick ith index\n\n\n\n\n# Complexity\n- Time complexity:$$O(n^2)$$\n\n- Space complexity:$$O(n^2)$$\n\n# Code\n```\nclass Solution {\n    int r = 1001,s1=0,s2=0;\n    int[][] dp;\n\n\n    private int func(List<Integer> nums1, List<Integer> nums2, int x, Integer[] ind, int i, int op){\n        if(op==0) return 0;\n        if(i==0){\n            if(op>0) return Integer.MIN_VALUE;\n            return 0;\n        }\n\n        if(dp[i][op]!=-1) return dp[i][op];\n\n        int a=0,b =0,c=0;\n        // In case we do not want to do op number of operations on whole array\n        a = func(nums1,nums2,x,ind,i,op-1);\n\n        // we decided to calculate maximum cut if we do op number of operations on whole array and we select ith index\n        b = nums1.get(ind[i-1])+ op*nums2.get(ind[i-1]) + func(nums1,nums2,x,ind,i-1,op-1);\n\n        // we decided to calculate maximum cut if we do op number of operations on whole array and we choose to skip ith index\n        c = func(nums1,nums2,x,ind,i-1,op);\n\n        int maxcut = Math.max(c,Math.max(a,b));\n        if(s1+s2*op-maxcut<=x){\n            r = Math.min(r,op);\n        }\n        return dp[i][op] = maxcut;\n    }\n    \n    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {\n        int n = nums1.size();\n\n        Integer[] ind = new Integer[n];\n\n        for(int i=0;i<n;i++){\n            s1+=nums1.get(i);\n            s2+=nums2.get(i);\n            ind[i] = i;\n        }\n\n        if(s1<=x) return 0;\n\n        //sort based on nums2\n        Arrays.sort(ind,(a,b)-> nums2.get(a)-nums2.get(b));\n\n        dp = new int[n+1][n+1];\n        for(int[] arr : dp) Arrays.fill(arr,-1);\n        func(nums1,nums2,x,ind,n,n);\n        return r<=n?r:-1;\n    }\n}\n```\n\n# Tabulation\n```\nclass Solution {\n    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {\n        int n = nums1.size(), s1=0, s2=0;\n\n        Integer[] ind = new Integer[n];\n\n        for(int i=0;i<n;i++){\n            s1+=nums1.get(i);\n            s2+=nums2.get(i);\n            ind[i] = i;\n        }\n\n        if(s1<=x) return 0;\n\n        Arrays.sort(ind,(a,b)-> nums2.get(a)-nums2.get(b));\n\n        int[][] dp = new int[n+1][n+1];\n        Arrays.fill(dp[0],Integer.MIN_VALUE);\n        dp[0][0] = 0;\n        \n        int r = n +1;\n        for(int i=1;i<=n;i++){\n            for(int j=1;j<=i;j++){\n                dp[i][j] = Math.max(nums1.get(ind[i-1])+ j*nums2.get(ind[i-1]) + dp[i-1][j-1],Math.max(dp[i][j-1],dp[i-1][j]));\n                if(s1+s2*j-dp[i][j]<=x){\n                    r = Math.min(r,j);\n                }\n            }\n        }\n        return r<=n?r:-1;\n    }\n}\n```
['Java']