N as sum of 1 to N

Posted on Posted in Algorithms

Given an integer N, print out number of ways to write N as sum of numbers from (1 to N) inclusive. Example: N = 5 Number of ways is 7 1+1+1+1+1 1+1+1+2 1+2+2 1+1+3 2+3 1+4 5 How do we do it recursively? Let’s See, Answer for N=4 is 5 1+1+1+1 1+1+2 2+2 1+3 4 To […]

Nth Fib Number – Dynamic Programming

Posted on Posted in Algorithms

Write a program that returns Nth Fib Number.  We are looking for an efficient solution that returns answer in less than 2 seconds if 1<= N <=50. Recursive Solution

Time Calculations

DP Solution (Top-Down)

Time Calculations

DP Solution (Bottom-Up)

Time Calculations

Happy Coding!!   Reference (Timer Functions)

 

Selling Wines Approach – Dynamic Programming

Posted on Posted in Algorithms

THUMB RULE We should first try to write a BRUTE-FORCE recursive solution (backtracking) with following best practices in mind.  Write a separate function that returns the answer.  Minimize the input parameters – Don’t pass the one that are constants (Size of array, array elements etc) – Rather make them global.  In the function modify only […]

Dynamic Programming

Posted on Posted in Algorithms

Dynamic Programming is one of the most-challenging algorithm design technique.  Most common choice for programming contests. Pre-Requisites Before reading further, please make sure that you are comfortable in writing recursive code especially for those problems where recursive formula isn’t given. Recursion Backtracking What does it take to master Dynamic Programming? Skill to figure out recursive formula […]