Rod Cutting (Dynamic Programming)

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 [...]

By |2018-05-27T22:08:59+05:30May 27th, 2018|Categories: Programming|Tags: |

Greedy technique vs Dynamic programming

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 [...]

By |2017-09-27T22:11:10+05:30September 27th, 2017|Categories: Data Structure|Tags: |

Coin Change

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 [...]

By |2019-03-02T16:40:50+05:30August 27th, 2017|Categories: Data Structure|Tags: |

Stairs Climbing Puzzle

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 [...]

By |2017-08-26T11:44:47+05:30August 26th, 2017|Categories: Data Structure|Tags: |

Counting Boolean Parenthesizations

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 [...]

By |2017-08-17T22:42:53+05:30August 17th, 2017|Categories: Miscellaneous|Tags: |

Matrix Chain Multiplication

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, [...]

By |2017-08-05T15:03:41+05:30August 5th, 2017|Categories: Data Structure|Tags: |

Dynamic programming approaches

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 [...]

By |2018-09-24T15:42:29+05:30March 29th, 2017|Categories: Data Structure|Tags: |
Go to Top