Dynamic Programming for beginners Online Webinar
Online Webinar on Dynamic Programming by Prateek Narang
Problem Solving Techniques
 Brute Force/ Complete Search
 Divide and Conquer
 Greedy Techniques
 Dynamic Programming
Dynamic Programming
“Those who cannot remember the past are condemned to repeat it.”
Dynamic Programing is all about remembering answers to the subproblems you’ve already solved and not solving it again.
Writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper.
"What's that equal to?"
Counting "Eight!"
Writes down another "1+" on the left.
"What about that?"
"Nine!" " How'd you know it was nine so fast?"
"You just added one more!"
"So you didn't need to recount because you remembered the
re were eight! Dynamic Programming is just a fancy way to
say remembering stuff to save time later!"
Where do we need Dynamic Programming?

If you are given a problem, which can be broken down into smaller subproblems.

These smaller subproblems can still be broken into smaller ones  and if you manage to find out that there are some overlappping subproblems.

So Dynamic Programming helps us to solve a particular class of problems with the following properties:
 Optimal Substructure
 Overlapping Subproblems
Overlapping Subproblems : If a problem has subproblems which are overlapping/same in nature then this is a big hint for dynamic programming.
Optimal Substructure : Optimal Substructure Property means if the optimal solution of the given problem can be formed using optimal solutions of its subproblems.
DP Vs Recursion
 Same Problems can be solved with Recursion and are based on principle of Mathematical Induction. But if the problems have overlapping subproblems then recursive solutions take more time
Divide & Conquer VS Dynamic Programming
We divide the problem in to nonoverlapping subproblems and solve them independently. But in case of dynamic programming the subproblems are overlapping in nature.

Example of Divide and Conquer  Binary Search, Square Root of a number using Binary Search

Example of Dynamic Programming  Computing Nth Fibonacci Number
DP vs Greedy
Lets discuss it through an example
Counting Money Problem
Suppose you want to count out a certain amount of money, using the fewest possible notes or coins.
Greedy Approach: At each step, take the largest possible note or coin that does not overshoot the sum of money and include it in the solution.
Example: To make Rs 39 with fewest possible notes or coins in Indian Currency.
```Rs 10 note, to make 29 Rs 10 note, to make 29 Rs 10 note, to make 19 Rs 10 note, to make 9 Rs 5 note, to make 4 Rs 2 coin, to make 2 Rs 2 coin, to make 0
Total is 4 notes and 2 coins, which is the optimum solution.
**Note**: For Indian currency, the greedy algorithm, even after demonetization always gives the optimum solution.
#### Is this true for any currency?
Now that Donald Trump is the new President of US, he decides to do
something extraordinary like PM Modi. So he decides to change all the currency notes to 1 dollars, 7 dollars and 10 dollars.
Suppose you went to US and used the same greedy approach to count
minimum numbers of notes and coins in exchange for a Burger which costs $15.
To make $15:
```1 $10 note
5 $1 notes
Total = 6 notes
Can we do better than 6?
$7 + $7 +$1 – Only 3 notes required!
DP is used in Optimization Problems
Dynamic Programming is typically applied to optimization problems. In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem.
Approaching Dynamic Programming
Top Down Approach
I will be an amazing coder. How?
I will work hard like crazy. How?
I'll practice more and try to improve. How?
I'll start taking part in contests. How?
I'll practicing. How?
I'm going to learn programming.
This approach is similar to recursion but the computed solutions to subproblems are stored in a table/array so that the overlapping subproblem is not computed again.
Top down is Recursion + Memoization

Dynamic programming is basically, recursion plus memoization

Recursion allows you to express the value of a function in terms of other values of that function. If you implement your function in a way that the recursive calls are done in advance, and stored for easy access, it will make your program faster. This is what we call Memoization  it is memorizing the results of some specific states, which can then be later accessed to solve other subproblems.
Bottom Up Approach
In Bottom Up, you start with the small solutions and then use these small solutions to build up larger solutions.
I'm going to learn programming.
Then, I will start practicing.
Then, I will start taking part in contests.
Then, I'll practice even more and try to improve.
After working hard like crazy,
I'll be an amazing coder.
Lets see an example.
Let us discuss Problems
Multiple Approaches, different time and space complexities.
Linear DP
1) Nth Fibonacci Number  Recursive Approach  Top Down Approach  Bottom Up Approach
2) Ladders Problem  Recursion  Top Down Approach  Bottom Up Approach
3) Min Coins Needed  Recursion  Bottom Up  DP vs Greedy Solution
4) Min Money Needed  Dynamic Programming Approach  Solve on HackerBlocks
Two dimensional DP
5) 01 Knapsack  Recursion  Bottom Up  DP vs Greedy solution
6) Unbounded Knapsack  Recursion  Bottom Up
7) Edit Distance  Recursion  Bottom Up  Homework  Solve on Spoj
 EDIST http://www.spoj.com/problems/EDIST/
Solutions
Ladders Problem
#include <iostream>
using namespace std;
// Recursion
int ways(int n){
//Ground
if(n==0){
return 1;
}
if(n<0){
return 0;
}
int ans = ways(n1) + ways(n2) + ways(n3);
return ans;
}
// Time O(k Power n)
int ways2(int n,int k){
if(n==0){
return 1;
}
if(n<0){
return 0;
}
int ans = 0;
for(int j=1;j<=k;j++){
ans += ways2(nj,k);
}
return ans;
}
// Top Down DP  Homework
// Bottom Up Dp O(nk)
int waysBU(int n,int k){
int *dp = new int[n];
dp[0] = 1;
for(int step=1;step<=n;step++){
dp[step] = 0;
for(int j=1;j<=k;j++){
if(stepj>=0){
dp[step] += dp[stepj];
}
}
}
return dp[n];
}
// Can we do it in O(n) ?
// Try doing it at home.
int main() {
int n = 4;
cout<<ways(n)<<endl;
cout<<ways2(3,2)<<endl;
cout<<ways2(4,3)<<endl;
cout<<ways2(5,4)<<endl;
cout<<waysBU(5,4)<<endl;
return 0;
}
Coin Change Problem
#include <iostream>
#include<climits>
using namespace std;
int coinsNeeded(int coins[],int amount,int n){
//Base Case
if(amount==0){
return 0;
}
//Rec Case
int ans = INT_MAX;
for(int i=0;i<n;i++){
// Think about it for 2 mins !
if(amountcoins[i]>=0){
int smallerAns = coinsNeeded(coins,amountcoins[i],n);
if(smallerAns!=INT_MAX){
ans = min(ans,smallerAns+1);
}
}
}
return ans;
}
// Bottom Up Dp
int coinsNeededDP(int coins[],int amount,int n){
int *dp = new int[amount+1];
for(int i=0;i<=amount;i++){
dp[i] = INT_MAX;
}
dp[0] = 0;
for(int rupay=1; rupay<=amount;rupay++){
// Iterate Over Coins
for(int i=0;i<n;i++){
if(coins[i]<=rupay){
int smallerAns = dp[rupaycoins[i]];
if(smallerAns!=INT_MAX){
dp[rupay] = min(dp[rupay],smallerAns + 1);
}
}
}
}
return dp[amount];
}
int main() {
int us_coins[] = {1,7,10};
int n = 3;
int amount = 15; // Ans should be 3
int indian_coins[] = { 1,2,5,10,50};
int paise = 13;
cout<<coinsNeeded(us_coins,amount,n)<<endl;
cout<<coinsNeeded(indian_coins,paise,5)<<endl;
cout<<"Using DP"<<endl;
cout<<coinsNeededDP(indian_coins,paise,5)<<endl;
cout<<coinsNeededDP(indian_coins,39,5)<<endl;
return 0;
}
Knapsack Problem
#include<iostream>
using namespace std;
int knapsack(int wts[],int prices[],int N,int W){
///Base Case
if(N==0W==0){
return 0;
}
///Rec Case
int inc= 0,exc=0;
if(wts[N1]<=W){
inc = prices[N1] + knapsack(wts,prices,N1,W wts[N1]);
}
exc = knapsack(wts,prices,N1,W);
return max(inc,exc);
}
int knapsackDP(int wt[],int price[],int N,int W){
int dp[100][100] = {0};
for(int n=0;n<=N;n++){
for(int w=0;w<=W;w++){
if(n==0w==0){
dp[n][w] = 0;
}
else{
int inc=0,exc = 0;
if(wt[n1]<=w){
inc = price[n1] + dp[n1][wwt[n1]];
}
exc = dp[n1][w];
dp[n][w] = max(inc,exc);
}
}
}
return dp[N][W];
}
int main(){
int wts[] = {2, 7, 3, 4};
int prices[ ] = {5,20,20,10};
int N = 4;
int W = 11;
cout<<knapsack(wts,prices,N,W)<<endl;;
cout<<knapsackDP(wts,prices,N,W)<<endl;
return 0;
}
Minimum Money Needed  HackerBlocks https://hack.codingblocks.com/contests/c/28/256
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
//freopen("test.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int n,k,b;
scanf("%d%d",&n,&k);
b = k;
int p[k +1];
int i,j;
for( i=1; i<=k; i++ )
scanf("%d",&p[i]);
int ans[k+1];
for(i=1; i<=k; i++)
{
ans[i] = p[i];
}
for(i=2; i<=k; i++)
{
for(j=1; j<i; j++)
{
if(p[ij] == 1  ans[j] == 1)
continue;
if(ans[i] == 1)
ans[i] = ans[j] + p[ij];
else
ans[i] = min(ans[i], ans[j] + p[ij]);
}
}
if(k==0)
printf("0\n");
else
printf("%d\n",ans[k]);
return 0;
}
Practice More Problems on www.hackerblocks.com