Define dynamic programming 

Dynamic programming (DP) is a method for solving problems by breaking them down into simpler subproblems and solving each subproblem just once, storing its solution to avoid redundant computations. It is particularly effective for optimization problems with overlapping subproblems and optimal substructure. DP typically involves defining a recursive relation for the problem, solving subproblems in a bottom-up manner, and using stored solutions to construct the final answer.