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:

Topdown 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.

Bottomup 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(n1) + F(n2), for n > 1
Bottomup 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[i1] + dp[i2]
}
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 bottomup 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(n1) + fibonacci(n2)
}
Output
0
1
1
2
3
5
8
13
21
34
55
In this implementation, we use the topdown 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[i1] + 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[i1] + 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:

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

Efficiency: Dynamic programming can significantly reduce the time complexity of a problem compared to bruteforce approaches.

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.