Dynamic Programming

Dynamic programming is a method for solving problems by breaking them down into smaller subproblems and storing the solutions to these subproblems for later use.

The key idea behind dynamic programming is to avoid solving the same subproblems multiple times by storing their solutions in a table or array. This allows us to reuse these solutions later when solving larger subproblems or the original problem.

Here, we use a loop tp compute the solutions to larger subproblems using the solutions to smaller subproblems.