Kadane’s Algorithm – Maximum Subarray Problem

Objective:  The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest … Read more

Dynamic Programming – Coin Change Problem

Objective: Given a set of coins and amount, Write an algorithm to find out how many ways we can make the change of the amount using the coins given.

This is another problem in which i will show you the advantage of Dynamic programming over recursion.

Example:

Amount = 5

coins [] = {1,2,3}

Ways to make change = 5

{1,1,1,1,1} {1,1,1,2}, {1,2,2}, {1,1,3} {2,3}

Approach:

Read more