CSD2183 Data Structures (2026) – lab_11_dynamic

Learning Objectives

By the end of this lab session, you should be able to:

Implement recursive and dynamic programming solutions to problems.
Understand the time complexity differences between naive recursion and optimized DP approaches.
Solve classic algorithmic problems such as Climbing Stairs, Longest Common Subsequence, and Coin Change.

Overview of Lab Activities

Here are the activities for which you will upload solutions to xSITe or Gradescope:

Climbing Stairs Problem - Recursive Solution: Submit using Gradescope. Total 25 marks.
Climbing Stairs Problem - Dynamic Programming Solution: Submit using Gradescope. Total 25 marks.
Longest Common Subsequence of 2 Strings: Submit using Gradescope. Total 25 marks.
Coin Change Problem: Submit using Gradescope. Total 25 marks.

Exercise 1A: Climbing Stairs Problem - Recursive Solution

Task

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. Given the value of n, your task is to calculate the number of distinct ways you can climb to the top. Code a recursive solution to this problem. Avoid using loops or arrays.

Examples

Input: n = 2
Output: 2
Explanation: (1 step + 1 step) OR (2 steps)

Input: n = 3
Output: 3
Explanation: (1 step + 1 step + 1 step) OR (1 step + 2 steps) OR (2 steps + 1 step)

Exercise 1A: Climbing Stairs Problem - Recursive Solution

Constraints

The parameter n can take values between 1 and 45 (inclusive).

Template

You can find the template files on GitHub here. Use the provided makefile to compile and run your project.

Submission

Implement the climbStairs function using recursion. Submit your completed climb_stairs_recursive.cpp file to the Gradescope assignment titled Week 11 Lab Exercise 1A: Climbing Stairs - Recursive Solution.

Exercise 1A: Climbing Stairs Problem - Recursive Solution

Solution

int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

Time Complexity

Each call to climbStairs(n) recursively calls climbStairs(n-1) and climbStairs(n-2). This creates a binary recursion tree, where each node branches into two subproblems. The total number of function calls grows exponentially, leading to \(T(n)=T(n−1)+T(n−2)+O(1)\) which resolves to \(O(2^n)\).

Space Complexity

The space complexity is \(O(n)\) due to recursion stack usage.

Exercise 1B: Climbing Stairs Problem - Bottom-Up Dynamic Programming Solution

Task

Requirements

Give a bottom-up dynamic programming solution to this problem (tabulation). You are encouraged to use arrays. Do NOT use recursion for this problem.

Example

Input: n = 4
Output: 5
Explanation: (1+1+1+1) OR (2+1+1) OR (1+2+1) OR (1+1+2) OR (2+2)

Exercise 1B: Climbing Stairs Problem - Dynamic Programming Solution

Constraints

The parameter n can take values between 1 and 45 (inclusive).

Template

You can find the template files on GitHub here.

Implement the climbStairsDP function using dynamic programming (bottom-up). Use either an array-based approach (O(n) space) or an optimized two-variable approach (O(1) space).

Submission

Submit your completed climb_stairs_dp.cpp file to the Gradescope assignment titled Week 11 Lab Exercise 1B: Climbing Stairs - DP Solution.

Exercise 1B: Climbing Stairs Problem - Dynamic Programming Solution

Array-Based Solution (O(n) Space)

int climbStairsDP(int n) {
    if (n <= 2) return n;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Time and Space Complexity

The time complexity of this DP solution is \(O(n)\) (big improvement from the previous recursive solution), and the space complexity is also \(O(n)\) (due to arrray usage).

Exercise 1B: Climbing Stairs Problem - Dynamic Programming Solution

Optimized Space Solution (O(1) Space)

int climbStairsDP(int n) {
    if (n <= 2) return n;
    int first = 1, second = 2, third;
    for (int i = 3; i <= n; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return third;
}

Time and Space Complexity

The time complexity of this DP solution is \(O(n)\) (big improvement from the previous recursive solution), and the space complexity is \(O(1)\) (better than previously).

Exercise 2: Longest Common Subsequence

Task

Given two strings text1 and text2, return the length of their longest common subsequence (LCS).

Definitions

A subsequence is a new sequence that can be formed from an existing sequence by deleting some characters without changing the order of the remaining characters. For example, for the string ABCDE, valid subsequences include AB, ACE, BDE. Strings like CA or EDB are NOT valid subsequences (order changed).

A common subsequence between text1 and text2 is a subsequence that appears in both strings. For example, the subsequence AE appears in both ABE and AFE.

The longest common subsequence between text1 and text2 is the a common subsequence that has maximum length.

Exercise 2: Longest Common Subsequence

Examples

Input: text1 = "abcde", text2 = "ace"
Output: 3  // longest common subsequence is "ace"

Input: text1 = "abcbdab", text2 = "bdcaba"
Output: 4  // longest common subsequence is "bcba"

Input: text1 = "abc", text2 = "def"
Output: 0  // No common subsequence between text1 and text2

Template

You can find the template files on GitHub here. Implement the longestCommonSubsequence function using dynamic programming with a 2D table. This table should store the length of the LCS for different prefixes of the input strings.

Submission

Submit your completed longest_common_subsequence.cpp file to the Gradescope assignment titled Week 11 Lab Exercise 2: Longest Common Subsequence.

Exercise 2: Longest Common Subsequence

Hints

Consider the prefixes of the strings text1 and text2. The longest common subsequence of the text1 and text2 depends on the longest common subsequence of their prefixes.
Use a 2D table to store the solutions to the subproblems instead of recursion. A table called LCS(i,j) should store the longest common subsequence of the prefix of text1 with length i and the prefix of text2 with length j.
If the last characters of the prefixes match, include them in the LCS and move to the previous characters: LCS(i,j)=LCS(i−1,j−1)+1.
If the last characters of the prefixes don’t match, try removing one character at a time and take the maximum result: LCS(i,j) = max(LCS(i−1,j),LCS(i,j−1)).

Exercise 2: Longest Common Subsequence

Hints

\[ LCS(i, j) = \begin{cases} 0, & \text{if } i = 0 \text{ or } j = 0 \\ LCS(i-1, j-1) + 1, & \text{if } text1[i-1] = text2[j-1] \\ \max(LCS(i-1, j), LCS(i, j-1)), & \text{if } text1[i-1] \neq text2[j-1] \end{cases} \]

The final solution is LCS[m][n], where m is the length of text1 and n is the length of text2.

Exercise 2: Longest Common Subsequence

Solution

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> LCS(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1])
                LCS[i][j] = 1 + LCS[i - 1][j - 1];
            else
                LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
        }
    }
    return dp[m][n];
}

Exercise 3: Coin Change Problem

Task

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount.

If that amount of money cannot be made up by any combination of the coins, return -1.

Examples

Input: coins = {1,2,5}, amount = 11
Output: 3  // (5+5+1)
Explanation: The fewest number of coins to make up 11 is 3, since 11 = 5 + 5 + 1. There are other ways to make up the value of 11 (like 5 + 2 + 2 + 2), but they require a higher number of coins.

Input: coins = {2}, amount = 3
Output: -1
Explanation: There is no way to make up an amount of 3 using only coins of denomination 2, so we return -1.

Exercise 3: Coin Change Problem

Template

You can find the template files on GitHub here.

Implement the coinChange function inside the partial coin_change.cpp file. Use a dynamic programming approach to solve this problem

Submission

Submit your completed coin_change.cpp file to the Gradescope assignment titled Week 11 Lab Exercise 3: Coin Change Problem.

Exercise 3: Coin Change Problem

Hints

Think in terms of choices. At each step, you can choose to take a coin or skip it.
For each subproblem (i=1, i=2 … i=n), try all possible choices and take the one with the fewest coins.
Break it down recursively. Let dp(amount) represent the minimum number of coins needed for amount. The recurrence relation is : dp(amount)=1+min(dp(amount−c)) for all c values in the coins array.
If no valid combination is found, return -1.

Exercise 3: Coin Change Problem

Solution

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    if (dp[amount] == amount + 1){
        return -1;
    }
    return dp[amount];
}