Sponsored
Sponsored
Solve with full IDE support and test cases
Use these hints if you're stuck. Try solving on your own first.
Sort the rewards array first.
If we decide to apply some rewards, it's always optimal to apply them in order.
Let <code>dp[i][j]</code> (true/false) be the state after the first <code>i</code> rewards, indicating whether we can get exactly <code>j</code> points.
The transition is given by: <code>dp[i][j] = dp[i - 1][j − rewardValues[i]]</code> if <code>j − rewardValues[i] < rewardValues[i]</code>.