N as sum of 1 to N

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

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 unsigned long long fib(int n){ if(n==1) return 0; if(n==2) return 1; return fib(n-1)+fib(n-2); } Time Calculations N_Fib : Answer : Time Taken 40th : 63245986 :…

Selling Wines Approach – Dynamic Programming

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…

Selling Wines Problem – Dynamic Programming

PROBLEM STATEMENT Given prices array of N bottles – P[N] of wine (not essentially in sorted order) arranged on shelf of a bar. Every year we’ve to sell one bottle of wine, Selling price of a bottle will be YEAR * P[i].  Assuming we start with YEAR=1. But constraint is that we can sell either leftmost…

Dynamic Programming

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…