Dynamic Programming (DP) is one of the algorithm design techniques that solves complex problems by breaking them down into simpler subproblems.
In this article, we will learn how to apply dynamic programming using the Swift language and have the opportunity to practice the theory through real algorithm problems.
Basics of Dynamic Programming
Dynamic programming is a method of solving a given problem by dividing it according to optimal substructure.
There are fundamentally two main elements: Memoization and Tabulation.
Memoization is a way to store the results of solved problems recursively to avoid redundant calculations,
while Tabulation involves storing the results of subproblems in a table to solve the problem in a bottom-up manner.
Problem Introduction: Fibonacci Sequence
The Fibonacci sequence is a sequence of natural numbers where the first two terms are 0 and 1,
and the subsequent terms are defined as the sum of the two preceding terms.
That is, F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2).
Let’s understand the concept of dynamic programming while implementing an efficient way to calculate the Fibonacci sequence.
Problem Solving Process
1. Understanding the Problem
This is a problem to find the nth term of the Fibonacci sequence.
There is a simple definition, but if implemented with a recursive method, redundant calculations occur, making it inefficient.
2. Applying Dynamic Programming
By using dynamic programming, we can avoid redundant calculations.
In particular, by storing and reusing previously computed results from subproblems, we can reduce the time complexity.
Here, we will solve the problem using the memoization approach.
3. Implementing Memoization
Memoization is a way of saving previously computed results by using additional variables in the recursive function.
Let’s write the code in Swift.
func fibonacci(_ n: Int, _ memo: inout [Int?]) -> Int {
if let value = memo[n] {
return value
}
if n <= 1 {
memo[n] = n
return n
}
memo[n] = fibonacci(n - 1, &memo) + fibonacci(n - 2, &memo)
return memo[n]!
}
func fibonacciWrapper(n: Int) -> Int {
var memo = Array(repeating: nil, count: n + 1)
return fibonacci(n, &memo)
}
// Example call
let result = fibonacciWrapper(n: 10)
print(result) // Output: 55
4. Analyzing Time Complexity
The time complexity of the Fibonacci sequence using memoization is O(n).
It demonstrates efficient performance because it computes each n only once and stores the results.
The space complexity is also O(n).
5. Implementing Using Tabulation Method
Now, let’s solve the same problem using the tabulation method.
This method approaches the problem in a bottom-up manner by storing the results of subproblems in a table.
Let’s write the code in Swift.
func fibonacciTabulation(_ n: Int) -> Int {
if n <= 1 { return n }
var dp = Array(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 call
let resultTabulation = fibonacciTabulation(n: 10)
print(resultTabulation) // Output: 55
6. Conclusion
In this article, we learned the basic concepts of dynamic programming using Swift and practiced the memoization and tabulation techniques through the Fibonacci sequence problem.
Dynamic programming is a powerful tool that can be applied to various algorithmic problems,
and understanding and applying the theory will greatly help in coding tests as well.