choose-numbers-from-two-arrays-in-range

< Previous 　　　　　　　　　　　　　　　　 Next >

2143. Choose Numbers From Two Arrays in Range (Hard)

Related Topics

[Array] [Dynamic Programming]

Hints

Hint 1

If you know the possible sums you can get for a range [l, r], how can you use this information to calculate the possible sums you can get for a range [l, r + 1]?

Hint 2

For the range [l, r], if it is possible to choose elements such that the sum of elements you picked from nums1 is x and the sum of elements you picked from nums2 is y, then (x + nums1[r + 1], y) and (x, y + nums2[r + 1]) are possible sums you can get in the range [l, r + 1].

Hint 3

How can we save the possible sums obtainable at a given index so that we can reuse this information later?