Edit Distance (Levenshtein Distance) Problem

Write a program to find the minimum number of operations required to convert string X to string Y. You have the following three operations permitted on a string: 1) Insert a character 2) Delete a character 3) Replace a character. The edit distance between two strings is the minimum number of operations (insertions, deletions, or substitutions of characters) required to transform one string into the other.

Climbing Stairs Problem

There is a staircase of n steps, and you can climb either 1 or 2 steps at a time. Write a program to count and return the number of unique ways to climb the nth stair. The order of steps taken matters. Note: Climbing stairs is an excellent problem to learn dynamic programming approach and application of the Fibonacci series in problem-solving.

Minimum Coin Change Problem

Suppose we want to make a change for a given value K of cents, and we have an infinite supply of each of coin[ ] = [C1, C2, …, Cm] valued coins. Write a program to find the minimum number of coins required to make the change. Note: This is an excellent counting problem to learn problem solving using dynamic programming approach.

Maximum Subarray Sum (Kadane’s Algorithm)

Given an array of n elements, write a program to find the largest contiguous subarray sum. A subarray of array X[] is a contiguous segment from X[i] through X[j] where 0 <= i <= j <= n. Note: This is an excellent problem to learn problem solving using divide and conquer approach, dynamic programming and single loop (In place O(n) time solution).

Minimum Number of Jumps to Reach End

An array of non-negative integers is given and the aim is to reach the last index in the minimum number of jumps. You are initially positioned at the first index of the array and each element in the array represents your maximum jump length at that position. Note: This is an excellent problem to learn problem solving using dynamic programming.

Longest Common Subsequence

Given two strings X[] and Y[] of size m and n, design an algorithm to find the length of longest common subsequence (LCS). There can be many possible common subsequences of two strings, but we need to return the common subsequence of longest length. Note: This is an excellent problem to learn dynamic programming.

Introduction to Dynamic Programming in DSA

Dynamic Programming is a popular problem solving approach in data structures and algorithms, which solve problems by combining subproblem solutions like divide and conquer. But rather than solving the same sub-problem again, DP solves sub-problems once and stores the calculated value in extra memory to avoid the recomputation.

Top-Down (Memoization) vs Bottom-up (Tabulation) in DP

Understanding differences between top down (memoization) and bottom up approach (tabulation) of dynamic programming will help us make critical decisions during problem-solving. One idea is common to both approaches: They use extra memory to store solutions to sub-problems, avoid recomputation and improve performance.

Dynamic Programming vs Divide and Conquer

Learning divide and conquer vs dynamic programming is one of the critical ideas in DSA. Both use a similar idea to break problems into subproblems and combine their solutions to get the final solution. There are lot of differences between both approaches in terms of the types of problems they solve, implementation, time and space complexity, etc.

Types of Problems Solved Using Dynamic Programming

There could be two popular categories of problems that can be solved using dynamic programming: 1) Optimization problem: Here we need to find an optimal solution (minimum, longest, shortest, etc.) from a large solution space 2) Counting problem: Here we need to count different ways to find all occurrences of a combinatorial pattern.

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.