Vanilla dynamic programming to understand the logic
This post is inspired by https://leetcode.com/problems/minimum-time-to-make-array-sum-at-most-x/solutions/3868304/simple-dp-in-c-java-python/ !\n# Intuition\n D
This post is inspired by https://leetcode.com/problems/minimum-time-to-make-array-sum-at-most-x/solutions/3868304/simple-dp-in-c-java-python/ !\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt is important to realize that the problem can be translated as: given j steps, and i rows (nums and their corresponding increaments), what is the largest sum we can get. This largest sum is the value that will be subtracted from the total.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nUse dynamic programming. Credit to the [post](https://leetcode.com/problems/minimum-time-to-make-array-sum-at-most-x/solutions/3868304/simple-dp-in-c-java-python/) referenced before. Here I use the vanilla dp approach for an easy understanding. To make it clear:\n\n1. outerloop for step numbers. For any given step numbers allowed, loop over numbers of rows we can choose. This is not necessary but will make the logic more clear.\n2. It is a bit tricky to understand why we need to sort the candidates (the numbers to delete) by their corresponding increaments. \n    * A way to think of it is, because you want to delete as much as you can. so given j steps, when it comes to delete the jth number (consider it as the last number you have), you want to delete it such that it has the possible largest accumulation. Therefore you have to sort the increments from small to last, in order to meet this criterion for every given J loop.\n    * (**Note:** indeed for a given J, you may have more candidates to choose, so deleting the jth number may not necessary give you the final answer; don\'t forget the number itself plays a role too, not just the increments. This is why in the dp, you see the maximum selection. But when j == n, you have no choice but to delete all the numbers, which means all the numbers are selected). \n\nTry print the dp matrix and you will see why.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n# Code\n```\nclass Solution {\n    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {\n        /*\n         * dp definition \n         * dp[i][j]: given (i + 1) numbers, we can delete j times, then what is the\n         * maximum we are able to delete\n         */\n        \n        int n = nums1.size();\n        int[][] dp = new int[n + 1][n + 1];\n        \n        Integer[] idxSortedByVal = new Integer[n];\n\n        // calculate the base\n        int base = 0;\n        int increase = 0;\n        for (int i = 0; i < n; i++) {\n            idxSortedByVal[i] = i;\n\n            base += nums1.get(i);\n            increase += nums2.get(i);\n        }\n\n        if (base <= x) {\n            return 0;\n        }\n\n        // sort is must, to ensure we delete the maximum increament\n        // at jth step, it is always best to delete a number with largest increament in the last step.\n        Arrays.sort(idxSortedByVal, (a, b) -> nums2.get(a) - nums2.get(b));        \n\n        for (int j = 1; j <= n; j++) {\n            for (int i = j; i <= n; i++) {\n                // how to get dp[i][j]:\n                // 1. we do nothing, use dp[i - 1][j]\n                // 2. we use this nums[i - 1]\n                // we have to compare and choose the max. \n                // This is because besides the increaments, the number also contributes to the dp[i][j], and they can "compete"\n                dp[i][j] = Math.max(dp[i - 1][j], \n                    dp[i - 1][j - 1] \n                    + nums1.get(idxSortedByVal[i - 1]) + j * nums2.get(idxSortedByVal[i - 1]));\n\n                int total = base + increase * j;\n\n                // System.out.printf("j: %d | i: %d | total: %d | dp[i][j]: %d%n", \n                //     j, i, total, dp[i][j]);\n\n                if (total - dp[i][j] <= x) {\n                    // meet the condition\n                    // System.out.printf("meet condition!");\n\n                    return j;\n                }\n            }\n        }\n\n        // impossible\n        return -1;\n\n    }\n}\n```
['Java']