Definitions
Let dp[k]
denotes the profit for selling k
apples in the optimal way
Let profit[k]
detones the profit for selling k
apples at once.
Recurrence relation
Clearly, dp[0] = 0
.
Then we can define, a recurrence relation as follows:
dp[k] = max{dp[i] + profit[k - i]}, where 0 <= i < k
You are interested in computing dp[n]
.
Conclusion
You can easily implement it using bottom-up approach or memoization and both method are pretty straighforward.
The time complexity of this solution is O(n^2)
, because computing a single entry in dp
array takes O(n)
time.