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.
1public class Solution {
2 public static int solveProblem(int n) {
3 int[] dp = new int[n + 1];
4 dp[0] = 1;
5 for (int i = 1; i <= n; i++) {
6 dp[i] = dp[i - 1] * 2;
7 }
8 return dp[n];
9 }
10
11 public static void main(String[] args) {
12 int n = 5;
13 System.out.println("Solution: " + solveProblem(n));
14 }
15}In this Java solution, a simple integer array is used to store results of subproblems, similar to C and C++ solutions. The base case is initialized, followed by iterative computation for each subsequent index.
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
class Solution {
static int SolveProblem(int n) {
if (n == 0) return 1;
return 2 * SolveProblem(n - 1);
}
static void Main() {
int n = 5;
Console.WriteLine("Solution: " + SolveProblem(n));
}
}In this C# solution, the recursive function invokes itself with smaller arguments until a base case of n equals zero is met.