can we solve the problem using one-D array.If yes how?

You can cut down the space usage significantly.

And the tester’s solution uses exactly that. Here’s the pseudo code.

```
FOR i -> 0 to W
G[i] = 0
ENDFOR
(*)FOR i -> 1 to N
FOR j -> W downto 0
G[j] = max(G[j + T[i]], G[j] + C[i] × P[i])
ENDFOR
```

In many DP problems, you just require the past few values so you can get rid of the *not-to-be-used-in-future* memory, and modify your code accordingly to save space. Specially when you require just the optimal answer and NOT a solution to the problem, where you need to *reconstruct the solution* from the final solution by guessing as which path you took so that you got the current answer, and so on.

EDIT: Link for the editorial.

got it…Thanks…earlier my j loop was running from j=0 to w and this was creating problem…but after going through the editorial i got my mistake…

glad. Good Luck