20 Lines Simple Bottom Up DP
Solution\nFor an optimal solution, if we have indices i1, i2... as a part of the optimal solution where we set the index to 0, then when doing the operation in 
# Solution\nFor an optimal solution, if we have indices i1, i2... as a part of the optimal solution where we set the index to 0, then when doing the operation in the problem, we should go in order of nums2[i1]<=nums2[i2]... because we want to pick the greatest value last and let the value accumulate before we set it to 0.\nThis is clearly DP since there are tons of cases and we have to make optimal decisions. Its not greedy because even though we go from the lowest nums2, we might not have to do an operation there. When picking which indices to set to 0, the total run time can be O(2^n). When thinking of how to structure DP, we may want to use 2D DP, but we then need to know the max amount of operations. \nTo help us get there, we should realize that for an optimal solution, we only have to set an index to 0 once. Proof: if we make the assumption that we have to do it twice, instead of doing it the first time, we could just do it the second time, and it would still go to 0, making it one less operation. Thus, we know the maximum number of operations is len(nums)\n\ndp[i][j] represents the minimum value after i operations after deleting nums[j\'] where j\' <= j . In other words, an optimal solution may never include deleting a number, and since we always delete in increasing order of j, if deleting nums2[j] is greater than a previous found number, then itll never be in the solution. \n\nThe transition fucntion is dp[i][j] = min(prev in dp[i], dp[i-1][j-1] - nums2[j] - i * nums1[j] + delta). In other words, subtract the accumulated numbers in that index, subtract the starting number, and then add delta.\n\n\n\n# Code\n```\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        dp = [[0] * (len(nums1)) for _ in range(len(nums1) + 1)]\n        start, delta = sum(nums1), sum(nums2)\n        if start <= x:\n            return 0\n        nums = [[n1, n2] for n1,n2 in zip (nums1, nums2)]\n        dp[0] = [start] * (len(nums1))\n        nums.sort(key = lambda s:(s[1], s[0]))\n\n        for i in range(1,len(nums) + 1):\n            minVal = float(\'inf\')\n            for j in range(len(nums)):\n                if i > j + 1:\n                    continue\n                minVal = min(minVal, dp[i-1][j-1] - i * nums[j][1] - nums[j][0] + delta)\n                dp[i][j] = minVal\n                if dp[i][j] <= x:\n                    return i\n        return -1\n        \n```
['Dynamic Programming', 'Python3']