Suppose we have a sequence of letters ACCGGTC. Then a subsequence of this sequence would be like ACCG or ACTC or CCC. To get ACTC, we pick letters 1, 2, 6, and 7. Formally, given a sequence X = x1, x2, . . . , xm, another sequence Z = [...]
Problem : Assume a company buys long steel rods and cuts them into shorter rods for sale to its customers. If each cut is free and rods of different lengths can be sold for different amounts, we wish to determine how to best cut the original rods to maximize the [...]
Both techniques use optimal substructure (optimal solution “contains optimal solution for subproblems within it”). In dynamic programming, solution depends on solution to subproblems. That is, compute the optimal solutions for each possible choice and then compute the optimal way to combine things together. In greedy algorithm we choose what looks [...]
Let' there are coins from 1 to N and the sum you are trying to get is SUM. Problem is basically finding in how many ways we can make the sum SUM using coins that have numbers from 1 to N. This problem can be solved using dynamic programming. Instead of thinking about [...]
A child going up a staircase with n steps, can hop up 1, 2, or 3 steps at a time. How many ways can the child reach the top? If there are zero steps, then there is one way for the child to climb the steps (i.e., do nothing.) If [...]
Given a boolean expression consisting of a string of the symbols True, False, AND, OR, and XOR, count the number of ways to parenthesize the expression such that it will evaluate to True. For example, there are 2 ways to parenthesize True AND False XOR True such that it evaluates [...]
Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming is applicable when the subproblems are not independent, that is, [...]
A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem. Typically, a greedy algorithm is used to solve a problem with [...]
Introduction Dynamic programming (DP) is a very powerful technique to solve a particular class of problems. The idea is very simple, if we have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again. If the given [...]
Minimum Edit distance between two strings str1 and str2 is defined as the minimum number of insert/delete/substitute operations required to transform str1 into str2. For example if str1 = "INTENTION", str2 = "EXECUTION", then the minimum edit distance between str1 and str2 turns out to be 5. Using dynamic programming, [...]