Explained DP 33ms
IntuitionThe key observation is that when zeroing multiple positions, we want to zero positions with higher growth rates (nums2[i]) later, since they contribute
# Intuition
The key observation is that when zeroing multiple positions, we want to zero positions with higher growth rates (nums2[i]) later, since they contribute more to the total sum over time. This leads to a dynamic programming solution where we consider positions in order of their growth rates.

# Approach
The solution uses dynamic programming to track the maximum possible reduction at each step. Key insights that make this work:

1. We never need to zero a position twice - if we zero at times t1 and t2, zeroing only at t2 gives the same result with fewer operations.

2. For optimal reduction, we process positions in order of increasing nums2[i] values. This is provably optimal because swapping the order of operations would result in more growth from higher-rate positions.

The dp array tracks maximum reduction possible using subsets of positions [0..p]. At each step s, for position p, we either:
- Skip position p (take previous best)
- Use p as the last operation (add reduction from initial value + growth over s steps)

We iterate through possible step counts until finding the minimum that achieves the target sum limit.

# Complexity
- Time complexity: $$O(n^2)$$ 

# Code
```cpp []
class Solution {
public:
    /** Core considerations:
     *  1. Key insight: Never need to zero a position twice because:
     *     - If we zero position i twice at t1 < t2
     *     - The ultimate reduction is same as zeroing only at t2
     *  2. For any chosen indices to zero out, it is optimal to process in order
     *     of increasing nums2[i]; proof: swapping operations in different
     *     order strictly reduces total reduction */
    int minimumTime(vector<int>& nums1, vector<int>& nums2, int sum_lim) {
        const int init_sum = accumulate(nums1.begin(), nums1.end(), 0);
        if (init_sum <= sum_lim) return 0;
        const int addit_sum = accumulate(nums2.begin(), nums2.end(), 0);

        const int N = nums1.size();
        vector<pair<int, int>> addit_inits(N);
        for (int i = 0; i < N; ++i)
            addit_inits[i] = { nums2[i], nums1[i] };
        sort(addit_inits.begin(), addit_inits.end());

        // dp[p] = max reduction possible using subset of positions [0..p]
        vector<int> dp(N), up_dp(N);

        // For each possible number of steps in solution
        for (int s = 1; s <= N; ++s) {
            int dp_base = 0, up_dp_base = 0;
            int max_up_dp = numeric_limits<int>::min() / 3;
            // For each position p, calculate max reduction if [0..p] items considered
            for (int p = 0; p < N; ++p) {
                up_dp[p] = max(
                    up_dp_base, // Consider skip zeroing position p
                    // Or zero it as the very last operation
                    dp_base + s * addit_inits[p].first + addit_inits[p].second);
                dp_base = dp[p];
                up_dp_base = up_dp[p];
                max_up_dp = max(max_up_dp, up_dp[p]);
            }
            // Early return if current step count achieves target sum
            if (init_sum + s * addit_sum - max_up_dp <= sum_lim) return s;
            swap(dp, up_dp);
        }

        return -1;
    }
};

```
['C++']