Dynamic Programming (DP) is a method used in computer science and mathematics to solve complex problems by breaking them down into simpler subproblems. The key idea is to solve each subproblem only once and store its solution, thereby avoiding redundant computations and improving efficiency.
Key Concepts of Dynamic Programming
Optimal Substructure: This property means that the optimal solution to a problem can be constructed from the optimal solutions of its subproblems. For example, in the Fibonacci sequence, the value of $$ F(n) $$ can be derived from $$ F(n-1) $$ and $$ F(n-2) $$[1][2][3][4][5].
Overlapping Subproblems: This property indicates that the problem can be broken down into subproblems which are reused several times. For instance, in the Fibonacci sequence, the subproblem $$ F(n-2) $$ is used in the computation of both $$ F(n) $$ and $$ F(n-1) $$[1][2][3][4][5].
Approaches in Dynamic Programming
Top-Down Approach (Memoization): This approach involves solving the problem recursively and storing the results of subproblems to avoid redundant calculations. It is essentially recursion combined with caching[1][2][3][4][5].
def fib(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
Bottom-Up Approach (Tabulation): This approach involves solving the problem iteratively and building up the solution from the base cases. It uses a table to store the results of subproblems[1][2][3][4][5].
def fib(n):
if n <= 1:
return n
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i-1] + table[i-2]
return table[n]
