Dynamic programming (DP) is a powerful technique used to solve complex problems by breaking them down into smaller subproblems. It is widely used in data structure and algorithm design to optimize solutions and improve efficiency. In this blog post, we’ll explore the concept of dynamic programming and see how it can be applied to solve problems using Swift code examples.

Understanding Dynamic Programming

Dynamic programming is based on the principle of solving problems by combining the solutions to smaller subproblems. The key idea is to store the results of subproblems to avoid redundant calculations and optimize the overall solution.

There are two main approaches to solving problems using dynamic programming:

1. Top-down approach (Memoization): Start with the main problem and recursively break it down into smaller subproblems. Store the results of subproblems in a memoization table to avoid redundant calculations.

2. Bottom-up approach (Tabulation): Start with the smallest subproblems and iteratively build up the solution to the main problem. Store the results of subproblems in a tabulation table.

Example: Fibonacci Sequence

Let’s consider the classic example of calculating the Fibonacci sequence using dynamic programming. The Fibonacci sequence is defined as follows:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), for n > 1

Bottom-up approach

func fibonacci(_ n: Int) -> Int {
  if n == 0 {
    return 0
  }
  if n == 1 {
    return 1
  }

  var dp = [Int](repeating: 0, count: n + 1)
  dp[0] = 0
  dp[1] = 1

  for i in 2...n {
    dp[i] = dp[i-1] + dp[i-2]
  }

  return dp[n]
}

// Example usage
print(fibonacci(0))
print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))
print(fibonacci(5))
print(fibonacci(6))
print(fibonacci(7))
print(fibonacci(8))
print(fibonacci(9))
print(fibonacci(10))

Output

0
1
1
2
3
5
8
13
21
34
55

In this implementation, we use the bottom-up approach to calculate the Fibonacci number at index n. We create a DP table dp to store the results of subproblems. We initialize the base cases dp[0] = 0 and dp[1] = 1. Then, we iterate from 2 to n and calculate each Fibonacci number by summing the previous two numbers stored in the DP table.

The time complexity of this solution is O(n), as we iterate from 2 to n once. The space complexity is also O(n) to store the DP table.

Top down approach

func fibonacci(_ n: Int) -> Int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

Output

0
1
1
2
3
5
8
13
21
34
55

In this implementation, we use the top-down approach to recursively calculate the nth fibonacci number. The time complexity is exponential, as every function calls two other functions. And the space complexity is O(n), as the maximum depth of the recursion tree is n.

Problems:

53. Maximum Subarray

Leetcode: 53. Maximum Subarray

Primary idea: Dynamic Programming, For each index i, DP[i] stores the maximum possible Largest Sum Contiguous Subarray ending at index i, and therefore we can calculate DP[i] using the mentioned state transition:

DP[i] = max(DP[i-1] + arr[i] , arr[i] )

Time Complexity: O(n), Space Complexity: O(n)

func maxSubArray(nums: [Int]) -> Int {
  var dp = Array<Int>(repeating: 0, count: nums.count)
  dp[0] = nums[0]
  var max_global = dp[0]

  for i in 1..<nums.count {
    dp[i] = max(nums[i], dp[i-1] + nums[i])
    max_global = max(max_global, dp[i])
  }

  return max_global
}

print(maxSubArray(nums: [1])) // 1
print(maxSubArray(nums: [-2,1,-3,4,-1,2,1,-5,4])) // 6
print(maxSubArray(nums: [5,4,-1,7,8])) // 23

Advantages of Dynamic Programming

Dynamic programming offers several advantages when solving problems:

1. Optimization: By storing the results of subproblems, dynamic programming avoids redundant calculations and optimizes the solution.

2. Efficiency: Dynamic programming can significantly reduce the time complexity of a problem compared to brute-force approaches.

3. Flexibility: Dynamic programming can be applied to a wide range of problems, including optimization problems, string manipulation, and graph algorithms.

Conclusion

Dynamic programming is a powerful technique for solving complex problems efficiently. By breaking down problems into smaller subproblems and storing their results, dynamic programming optimizes solutions and improves performance. Whether you’re working with data structures or algorithms, understanding dynamic programming is essential for designing efficient solutions.