Introduction to Dynamic Programming

Dynamic Programming is a popular problem-solving approach in data structures and algorithms, where we solve problems by combining the solutions to subproblems like the divide-and-conquer method. But rather than computing the same sub-problem repeatedly, we solve the sub-problem once and store the calculated value in extra memory to avoid the recomputation.

Climbing Stairs Problem

There is a staircase of n steps and you can climb either 1 or 2 steps at a time. You need to count and return the total number of unique ways to climb the staircase. The order of steps taken matters.

Minimum Coin Change Problem

If 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?

Maximum Subarray Sum (Kadane’s Algorithm)

Given an array X[] with n elements, we need to write a program to find the largest contiguous subarray sum. A subarray of array X[] of length n is a contiguous segment from X[i] through X[j] where 0<= i <= j <= n. Kadane algorithm idea is intuitive, using a single loop and few variables to solve the problem. We can use a similar idea to solve other coding problems.

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.

Top-Down vs Bottom-up approach in Dynamic Programming

There are two ways to solve and implement dynamic programming problems: 1) The top-down approach (Memoization) and 2) The bottom-up approach (Tabulation). Both approaches perform similarly in one way: They use extra memory to store the solution to sub-problems, avoid the recomputation and improve the performance by a huge margin. On another side, both of them are different in so many ways, and understanding this difference would help us to make critical decisions during problem-solving.

Dynamic programming vs. Divide and Conquer Approach

Divide and conquer and dynamic programming are popular problem-solving approaches in data structure and algorithms. Both approaches look similar in one way: They use a similar idea to break problems into subproblems and combine their solutions to obtain the solution to the original problem. But there are a lot of differences between both approaches.

What common problems are solved using dynamic programming?

There could be various patterns of dynamic programming problems. In practice, there are two popular categories of problems that can be solved using dynamic programming: 1) Optimization problems and 2) Counting problems.

Longest Common Subsequence

The longest common subsequence algorithm is a problem to find the length of the longest subsequence common to all subsequences of two strings. The lcs algorithm differs from the algorithm of the longest common substring problem. Explore and Enjoy!

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