Dynamic Programming in C++: A Deep Dive

Dynamic programming is a problem-solving paradigm where we break down a problem into simpler sub-problems. Let's delve into it using C++.

Steps for Dynamic Programming:

1. Identify States and Transient Function: Determine the states of the problem and create a function that defines the relationship between these states.
2. Initial Conditions & Boundary: Set the starting conditions and any boundary constraints.
3. Calculation Sequence: Outline the order in which calculations will occur.

---

Case Study 1: Minimum Coin Combination

Problem: Given coins of different denominations and a total amount, find the fewest number of coins to make up that amount.

Example: For coins = [1, 2, 5] and amount = 11, the answer is 3 (11 = 5 + 5 + 1).

Solution:

1. States & Transient Function:
   • Define $�[�]$ as the fewest number of coins to make up x.
   • $�[�]=\min (�[�-1],�[�-2],�[�-5])+1$.
2. Initial Conditions:
   • $�[1]=1$; $�[2]=1$; $�[5]=1$. Any $�[�]$ other than these is set to INT_MAX.
3. Calculation Sequence: Iterate from 1 to the desired amount, updating the coin count.

[code]

#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int minCoinumber(int Money)
{
    vector<int> D (Money+1, INT_MAX);
    D[2] = 1; D[1] = 1;  D[5] = 1;
    for( int i= 0; i<= Money; i++) {
       D[i] = min(D[i-2], min(D[i-3], D[i-5])) + 1;
    }
    return D[Money];
}

Case Study 2: 0/1 Knapsack Problem
Problem: Given items with weights and values, determine the maximum value we can fit in a knapsack of a given capacity.
Example: A knapsack can hold 5 lb at max. Items:
a: 1 lb, $6
b: 2 lb, $10
c: 3 lb, $12
Solution:
States & Transient Function:
Define $�[�][�]$ as the max value of i items for a knapsack that can hold weight j.
$�[�][�]=\max (�[�-1][�],�[�-1][�-\text{weight}[�]]+\text{value}[�])$.
Initial Conditions: $�[0][�]=0$ for all j.
Calculation Sequence: Iterate over items and capacities to fill the table.
[code]

#include<iostream>
#include<vector>

using namespace std;

const int N = 3;

vector <int> value = { 0, 6, 10, 12};
vector <int> weight = { 0, 1, 2, 3};

int Knapsack(int v) // v is the capacity of the knapsack
{
    vector< vector<int> > S (N+1, vector<int> (v, 0));   // 1) initial states
    int i,j;
    for (i = 1; i<= N; i++) {     
       for (j = 1; j<=v; j++) {      // from 1 to V 

          // state transcient function
           if ( j< weight[i])  S[i][j] = S[i-1][j] ;  
           else  S[i][j] = max(S[i-1][j], S[i-1][j-weight[i]] + value[i]);
    
       }
    }
    return S[N][v];
}

Conclusion: Dynamic programming allows for efficient problem solving by breaking problems into smaller sub-problems. Using C++, we can effectively implement solutions, ensuring optimal performance. Happy coding!