Dynamic Programming Problems

Xiao Jiang
Jul 22, 2017 · 6 min read

Coin Change Problem Minimum Number of Coins For Sum

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S.

First let’s find a sub-solution for this problem. To find the solution for i(i<S), for each coin j, Vj≤i, look at the minimum number of coins found for the i-Vj sum. Let this number be m. If m+1 is less than the minimum number of coins already found for current sum i, then we write the new result for it.

Another approach is to update the best solution yet found for a sum i, whenever a better solution for this sum was found.

Coin Change Problem Number of Ways to Make The Change

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

To count total number solutions, we can divide all set solutions in two sets. 1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.
Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

Longest non-decreasing sequence

Given a sequence of N numbers — A[1] , A[2] , …, A[N] . Find the length of the longest non-decreasing sequence.

Let L(i) be the length of the LIS ending at index i such that A[i] is the last element of the LIS. The time complexity for this solution is O(n2).

There’s a O(nlogn) solution: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Longest Common Subsequence

Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[m], Y[n]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[m], Y[n]).

Printing Longest Common Subsequence

Largest Sum Contiguous and Non-Contiguous Subarray

Find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

Edit Distance

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.

  1. Insert
  2. Remove
  3. Replace

All of the above operations are of equal cost.

  1. If last characters of two strings are same, nothing much to do. Ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1.
  2. Else (If last characters are not same), we consider all operations on ‘str1’, consider all three operations on last character of first string, recursively compute minimum cost for all three operations and take minimum of three values.
  3. Insert: Recur for m and n-1
  4. Remove: Recur for m-1 and n
  5. Replace: Recur for m-1 and n-1

0–1 Knapsack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0–1 property).

Optimal Substructure

To consider all subsets of items, there can be two cases for every item

1. The item is included in the optimal subset

2. The item is not included in the optimal subset

If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility

Optimal Strategy for a Game

Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

  1. The user chooses the ith coin with value Vi: The opponent either chooses (i+1)th coin or jth coin. The opponent intends to choose the coin which leaves the user with minimum value.
    i.e. The user can collect the value Vi + min(F(i+2, j), F(i+1, j-1) )
  2. The user chooses the jth coin with value Vj: The opponent either chooses ith coin or (j-1)th coin. The opponent intends to choose the coin which leaves the user with minimum value.
    i.e. The user can collect the value Vj + min(F(i+1, j-1), F(i, j-2) )

Count number of ways to cover a distance

Partition Problem Minimum Difference

Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

The problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array dp[n+1][sum+1] where n is number of elements in given set and sum is sum of all elements. We can construct the solution in bottom up manner.

Partition Problem

Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.

The problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array part[][] of size (sum/2)*(n+1). And we can construct the solution in bottom up manner such that every filled entry has following property

Count Number of Ways to Cover a Distance

Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps.

Minimum number of jumps to reach end

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element.

Min Cost Path

Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.

    Xiao Jiang

    Written by

    Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
    Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
    Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade