Dynamic Programming - DSA Interview Questions

Dynamic Programming (DP) is a powerful optimization technique used for solving overlapping subproblems and optimal substructure problems efficiently. It is widely used in coding interviews to solve complex recursive problems by breaking them into smaller subproblems and storing results to avoid redundant calculations.

Practice Dynamic Programming DSA Coding Problems with Solutions

Learning Objectives:

Understand the core concepts of Dynamic Programming, such as memoization (top-down) and tabulation (bottom-up). Learn how to recognize optimal substructure and overlapping subproblems in real-world coding problems.

Exercise Instructions:

Start with the first problem and attempt to solve it before checking the hint or solution.
Ensure you understand the logic behind each solution, as this will help you with more complex problems.
Use these exercises to reinforce your learning and identify areas that may require further study.

1. Fibonacci Number

Required Input:

Expected Output:

Code In Python

def fibonacci(n): # Write your code here pass # Predefined Input n = 6 # Output print(fibonacci(n))

Run Code?

Click Run Button to view compiled output

2. Climbing Stairs

Required Input:

Expected Output:

Code In Python

def climb_stairs(n): # Write your code here pass # Predefined Input n = 5 # Output print(climb_stairs(n))

Run Code?

Click Run Button to view compiled output

3. Unique Paths in a Grid

Required Input:

3 , 3

Expected Output:

Code In Python

def unique_paths(m, n): # Write your code here pass # Predefined Input m, n = 3, 3 # Output print(unique_paths(m, n))

Run Code?

Click Run Button to view compiled output

4. Min Cost Climbing Stairs

Required Input:

10 15 20

Expected Output:

Code In Python

def min_cost_climbing_stairs(cost): # Write your code here pass # Predefined Input cost = [10, 15, 20] # Output print(min_cost_climbing_stairs(cost))

Run Code?

Click Run Button to view compiled output

5. House Robber

Required Input:

2 7 9 3 1

Expected Output:

Code In Python

def house_robber(nums): # Write your code here pass # Predefined Input nums = [2, 7, 9, 3, 1] # Output print(house_robber(nums))

Run Code?

Click Run Button to view compiled output

6. Coin Change

Required Input:

1 2 5
11

Expected Output:

Code In Python

def coin_change(coins, amount): # Write your code here pass # Predefined Input coins = [1, 2, 5] amount = 11 # Output print(coin_change(coins, amount))

Run Code?

Click Run Button to view compiled output

7. Longest Common Subsequence

Required Input:

abcde
ace

Expected Output:

Code In Python

def lcs_length(s1, s2): # Write your code here pass # Predefined Input s1 = "abcde" s2 = "ace" # Output print(lcs_length(s1, s2))

Run Code?

Click Run Button to view compiled output

8. Edit Distance

Required Input:

horse
ros

Expected Output:

Code In Python

def edit_distance(word1, word2): # Write your code here pass # Predefined Input word1 = "horse" word2 = "ros" # Output print(edit_distance(word1, word2))

Run Code?

Click Run Button to view compiled output

9. Partition Equal Subset Sum

Required Input:

1 5 11 5

Expected Output:

True

Code In Python

def can_partition(nums): # Write your code here pass # Predefined Input nums = [1, 5, 11, 5] # Output print(can_partition(nums))

Run Code?

Click Run Button to view compiled output

10. Maximum Subarray Sum

Required Input:

-2 1 -3 4 -1 2 1 -5 4

Expected Output:

Code In Python

def max_subarray(nums): # Write your code here pass # Predefined Input nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] # Output print(max_subarray(nums))

Run Code?

Click Run Button to view compiled output

1 of 3