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

2017-09-27T22:11:10+05:30Categories: 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 [...]

2019-03-02T16:40:50+05:30Categories: Data Structure|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, [...]

2017-08-05T15:03:41+05:30Categories: 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 [...]

2018-09-24T15:42:29+05:30Categories: Data Structure|Tags: |
Go to Top