Category: Swift Coding Test

Problem Definition

We will address an algorithm problem that minimizes the number of coins needed to make a given amount
based on the types of coins available. For example, if the types of coins are
[1, 5, 10, 25] and the amount is 7,
the number of coins needed is 3 (5 + 1 + 1).

Input

• An array coins containing the types of coins (in int[] format).
• The target amount amount (of int type).

Output

Returns the minimum number of coins. Returns -1 if it is not possible.

Approach to the Problem

This problem can be approached using Dynamic Programming.
The goal is to repeatedly use coins to create the given amount and find the minimum count.
We utilize the properties of optimal substructure and overlapping subproblems with dynamic programming.

Step 1: Initialize the DP Table

First, create an array dp to store the minimum number of coins for each index i.
Initialize dp[0] to 0 and the rest to infinity.

Step 2: Update the DP Table

Loop through each coin and update the amount that can be made with that coin.
Each amount i is updated from the previous amount i - coin
by adding +1 to the coin count.

Swift Code Implementation

            func minCoins(coins: [Int], amount: Int) -> Int {
                // Initialize the DP table
                var dp = Array(repeating: Int.max, count: amount + 1)
                dp[0] = 0

                // Update the DP table
                for coin in coins {
                    for i in coin...(amount) {
                        if dp[i - coin] != Int.max {
                            dp[i] = min(dp[i], dp[i - coin] + 1)
                        }
                    }
                }

                return dp[amount] == Int.max ? -1 : dp[amount]
            }

            // Example usage
            let coins = [1, 5, 10, 25]
            let amount = 7
            let result = minCoins(coins: coins, amount: amount)
            print("Minimum number of coins: \(result)")
        

Time Complexity Analysis

The time complexity of this algorithm is O(m * n).
Here, m is the number of types of coins, and n is the target amount.
The outer loop iterates over the types of coins, and the inner loop iterates over the target amount,
resulting in two nested loops.

Additional Problems and Variations

This problem can be modified to add various requirements.
For example, there may be variations where only specific coins must be used,
or coins cannot be used multiple times.
It is also important to consider such variations.

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.