Determine the final answer
You process all values from up to using the formula
The final answer to the problem is simply
This solution runs in time and uses space, where is the maximum value in the input. The structure is exactly the same as in the previous problems: define the state, find the transition, set the base cases, and read the final answer from the appropriate state.