Data Structure Dynamic Programming Practice Questions with Solutions

By /

Introduction

Dynamic Programming (DP) is a problem-solving technique used when a problem can be divided into smaller overlapping problems. Instead of solving the same problem again and again, DP stores previous results and reuses them. In this chapter, you will practice Dynamic Programming through 10 solved JavaScript questions covering Fibonacci, climbing stairs, minimum cost, knapsack, coin change, and other common DP problems. Data Structure Dynamic Programming practice questions with solutions help to understand the concepts.

Question 1: Find Fibonacci Number Using Dynamic Programming

Question

Find the 10th Fibonacci number using Dynamic Programming.

function fibonacci(n) {
    let dp = new Array(n + 1).fill(0);

    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(fibonacci(10));

Solution

The DP array stores previously calculated Fibonacci numbers.

  • dp[0] = 0
  • dp[1] = 1
  • Every next value is calculated using the previous two values.
  • The result is stored and reused.

Output

55

Question 2: Count Ways to Climb Stairs

Question

A person can climb either 1 or 2 stairs at a time. Find the number of different ways to reach the 5th stair.

function climbStairs(n) {
    let dp = new Array(n + 1).fill(0);

    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(climbStairs(5));

Solution

To reach stair i, we can come from:

  • Stair i - 1
  • Stair i - 2

Therefore:

dp[i] = dp[i - 1] + dp[i - 2]

Output

8

Question 3: Find Minimum Cost to Reach the End

Question

Given the cost of each stair, find the minimum cost required to reach the top.

function minCostClimbingStairs(cost) {
    let n = cost.length;
    let dp = new Array(n + 1).fill(0);

    dp[0] = 0;
    dp[1] = 0;

    for (let i = 2; i <= n; i++) {
        dp[i] = Math.min(
            dp[i - 1] + cost[i - 1],
            dp[i - 2] + cost[i - 2]
        );
    }

    return dp[n];
}

console.log(minCostClimbingStairs([10, 15, 20]));

Solution

For every stair, we check whether reaching it from the previous stair or the stair before that costs less.

The smaller cost is stored in dp[i].

Output

15

Question 4: Solve 0/1 Knapsack Problem

Question

A bag can carry a maximum weight of 5. Find the maximum value that can be carried.

function knapsack(weights, values, capacity) {
    let n = weights.length;
    let dp = Array.from(
        { length: n + 1 },
        () => new Array(capacity + 1).fill(0)
    );

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                    dp[i - 1][w]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

let weights = [2, 3, 4];
let values = [40, 50, 60];

console.log(knapsack(weights, values, 5));

Solution

The algorithm checks every item and every possible capacity.

For each item, we have two choices:

  • Include the item.
  • Do not include the item.

The better value is stored in the DP table.

Output

90

Question 5: Find Number of Ways to Make a Target Amount

Question

Using coins [1, 2, 5], find how many different ways can be used to make the amount 5.

function coinChangeWays(coins, amount) {
    let dp = new Array(amount + 1).fill(0);

    dp[0] = 1;

    for (let coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

console.log(coinChangeWays([1, 2, 5], 5));

Solution

dp[i] represents the number of ways to create amount i.

Starting with:

dp[0] = 1

Each coin updates the possible amounts.

Output

4

The four combinations are:

5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Question 6: Find Minimum Number of Coins

Question

Using coins [1, 3, 4], find the minimum number of coins required to make amount 6.

function minCoins(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);

    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(
                    dp[i],
                    dp[i - coin] + 1
                );
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(minCoins([1, 3, 4], 6));

Solution

For every amount, we try every available coin.

For example:

6 = 3 + 3

requires only 2 coins.

The DP table keeps the minimum number found for every amount.

Output

2

Question 7: Find Maximum Sum Without Taking Adjacent Elements

Question

Find the maximum sum from an array without selecting two adjacent elements.

function maxNonAdjacentSum(arr) {
    let n = arr.length;

    if (n === 0) return 0;
    if (n === 1) return arr[0];

    let dp = new Array(n).fill(0);

    dp[0] = arr[0];
    dp[1] = Math.max(arr[0], arr[1]);

    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(
            dp[i - 1],
            dp[i - 2] + arr[i]
        );
    }

    return dp[n - 1];
}

console.log(maxNonAdjacentSum([2, 7, 9, 3, 1]));

Solution

At every position, we have two choices:

  • Skip the current number.
  • Take the current number and skip the previous number.

Therefore:

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

Output

12

One possible selection is:

2 + 9 + 1 = 12

Question 8: Find Longest Increasing Subsequence Length

Question

Find the length of the longest increasing subsequence in the array.

function longestIncreasingSubsequence(arr) {
    let n = arr.length;
    let dp = new Array(n).fill(1);

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp);
}

console.log(
    longestIncreasingSubsequence([10, 9, 2, 5, 3, 7, 101, 18])
);

Solution

dp[i] represents the length of the longest increasing subsequence ending at index i.

For every element, we compare it with all previous elements.

If the current element is larger, we can extend the previous subsequence.

Output

4

One longest increasing subsequence is:

2, 3, 7, 101

Question 9: Find Minimum Path Sum in a Grid

Question

Find the minimum sum path from the top-left corner to the bottom-right corner. You can move only right or down.

function minPathSum(grid) {
    let rows = grid.length;
    let cols = grid[0].length;

    let dp = Array.from(
        { length: rows },
        () => new Array(cols).fill(0)
    );

    dp[0][0] = grid[0][0];

    for (let i = 1; i < rows; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    for (let j = 1; j < cols; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            dp[i][j] = grid[i][j] +
                Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[rows - 1][cols - 1];
}

let grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
];

console.log(minPathSum(grid));

Solution

To reach each cell, we can come from:

  • The cell above.
  • The cell on the left.

We select the smaller path and add the current cell’s value.

Output

7

The minimum path is:

1 → 3 → 1 → 1 → 1

Total:

7

Question 10: Find Maximum Profit from House Robbery

Question

A person wants to rob houses. Each house contains a certain amount of money. Two adjacent houses cannot be robbed. Find the maximum amount that can be collected.

function robHouses(money) {
    let n = money.length;

    if (n === 0) return 0;
    if (n === 1) return money[0];

    let dp = new Array(n).fill(0);

    dp[0] = money[0];
    dp[1] = Math.max(money[0], money[1]);

    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(
            dp[i - 1],
            dp[i - 2] + money[i]
        );
    }

    return dp[n - 1];
}

console.log(robHouses([2, 7, 9, 3, 1]));

Solution

For every house, we decide whether to:

  • Skip the current house.
  • Rob the current house and skip the previous house.

The larger amount is stored in the DP array.

Output

12

The selected houses can contain:

2 + 9 + 1 = 12

Key Takeaways

  • Dynamic Programming stores results of smaller problems.
  • DP helps avoid repeated calculations.
  • A DP solution usually has a state, transition, and base case.
  • Fibonacci is a simple example of DP.
  • The climbing stairs problem uses previously calculated results.
  • Knapsack is a common Dynamic Programming problem.
  • Coin Change can be solved using DP.
  • Grid problems can use a 2D DP table.
  • Many optimization problems can be solved using DP.
  • DP is different from Greedy Algorithms because DP considers multiple possible choices before finding the best result.
  • Two common DP approaches are Memoization and Tabulation.

FAQs

1. What is Dynamic Programming in Data Structures?

Dynamic Programming is an algorithmic technique that solves a large problem by solving smaller overlapping problems and storing their results for reuse.

2. Why is Dynamic Programming useful?

It prevents the same subproblem from being calculated repeatedly, which can significantly improve performance.

3. What are the main parts of a DP problem?

Most DP problems involve identifying the state, base cases, transitions between states, and the final answer.

4. What is Memoization?

Memoization is a top-down DP approach where recursive results are stored so that the same calculation does not need to be performed again.

5. What is Tabulation?

Tabulation is a bottom-up DP approach where smaller solutions are calculated first and stored in a table until the final solution is reached.

6. Is Dynamic Programming the same as Greedy Algorithms?

No. Greedy algorithms usually make the best choice at the current step, while Dynamic Programming evaluates combinations of smaller subproblems to find an overall optimal solution.

7. Which problems commonly use Dynamic Programming?

Common examples include Fibonacci, Knapsack, Coin Change, Climbing Stairs, Longest Increasing Subsequence, Grid Path problems, and many optimization problems.

Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.

Related Posts

Scroll to Top