Sponsored
Sponsored
This approach involves breaking down the problem into overlapping subproblems, solving each subproblem only once, and storing their solutions - typically in a table. This can help reduce redundant calculations and improve efficiency.
Time Complexity: O(n), as each subproblem from 1 to n is solved once.
Space Complexity: O(n), due to the storage of results in the dp array.
1def solve_problem(n):
2 dp = [1] * (n + 1)
3 for i in range(1, n + 1):
4 dp[i] = dp[i - 1] * 2
5 return dp[n]
6
7n = 5
8print("Solution:", solve_problem(n))Python makes array (list) operations simple. Here, a list is initialized with base case values, and using a for-loop, each subsequent subproblem solution is calculated using the previous value.
A recursive approach solves the problem by solving smaller instances of the same problem. While this is a straightforward approach, it may lead to inefficiencies without memoization or optimizations because it can repeatedly solve the same subproblems.
Time Complexity: O(2^n), due to many duplicate subproblem calculations without memoization.
Space Complexity: O(n), considering the call stack.
1
This recursive C solution calls itself with a reduced problem size until it hits the base case. Each call multiplies the return value by 2.