Dynamic Programming

---

Data Structures and Algorithms (DSA) in C++: Dynamic Programming

Dynamic Programming (DP) is an optimization technique used to solve complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations. It is particularly useful for problems that have overlapping subproblems and optimal substructure properties.

Dynamic Programming can be implemented in two main ways:

1. Top-Down Approach (Memoization): This involves solving the problem recursively and storing the results of the subproblems in a table (usually an array or hashmap) to avoid recomputation.
2. Bottom-Up Approach (Tabulation): This involves solving the problem iteratively and building up the solution by solving smaller subproblems first and using their solutions to solve larger subproblems.

Classic Dynamic Programming Problems

1. Fibonacci Sequence
2. Longest Common Subsequence
3. 0/1 Knapsack Problem
4. Coin Change Problem
5. Edit Distance (Levenshtein Distance)

Example 1: Fibonacci Sequence

Top-Down Approach (Memoization)

        #include 
          #include 
          
          int fibonacci(int n, std::vector& memo) {
              if (n <= 1) {
                  return n;
              }
              if (memo[n] != -1) {
                  return memo[n];
              }
              memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
              return memo[n];
          }
          
          int main() {
              int n = 10;
              std::vector memo(n + 1, -1);
              std::cout << "Fibonacci of " << n << " is " << fibonacci(n, memo) << std::endl;
              return 0;
          }
          
      

Bottom-Up Approach (Tabulation)

        #include 
          #include 
          
          int fibonacci(int n) {
              if (n <= 1) {
                  return n;
              }
              std::vector dp(n + 1);
              dp[0] = 0;
              dp[1] = 1;
              for (int i = 2; i <= n; ++i) {
                  dp[i] = dp[i - 1] + dp[i - 2];
              }
              return dp[n];
          }
          
          int main() {
              int n = 10;
              std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
              return 0;
          }
      

Example 2: Longest Common Subsequence (LCS)

Top-Down Approach (Memoization)

        #include 
          #include 
          #include 
          
          int lcs(const std::string& X, const std::string& Y, int m, int k, std::vector>& memo) {
              if (m == 0 || k == 0) {
                  return 0;
              }
              if (memo[m][k] != -1) {
                  return memo[m][k];
              }
              if (X[m - 1] == Y[k - 1]) {
                  memo[m][k] = 1 + lcs(X, Y, m - 1, k - 1, memo);
              } else {
                  memo[m][k] = std::max(lcs(X, Y, m - 1, k, memo), lcs(X, Y, m, k - 1, memo));
              }
              return memo[m][k];
          }
          
          int main() {
              std::string X = "AGGTAB";
              std::string Y = "GXTXAYB";
              int m = X.size();
              int k = Y.size();
              std::vector> memo(m + 1, std::vector(k + 1, -1));
              std::cout << "Length of LCS is " << lcs(X, Y, m, k, memo) << std::endl;
              return 0;
          }
      

Bottom-Up Approach (Tabulation)

        #include 
          #include 
          #include 
          
          int lcs(const std::string& X, const std::string& Y) {
              int m = X.size();
              int k = Y.size();
              std::vector> dp(m + 1, std::vector(k + 1, 0));
          
              for (int i = 1; i <= m; ++i) {
                  for (int j = 1; j <= k; ++j) {
                      if (X[i - 1] == Y[j - 1]) {
                          dp[i][j] = dp[i - 1][j - 1] + 1;
                      } else {
                          dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
                      }
                  }
              }
              return dp[m][k];
          }
          
          int main() {
              std::string X = "AGGTAB";
              std::string Y = "GXTXAYB";
              std::cout << "Length of LCS is " << lcs(X, Y) << std::endl;
              return 0;
          }
      

Example 3: 0/1 Knapsack Problem

Top-Down Approach (Memoization)

        #include 
          #include 
          
          int knapsack(int W, const std::vector& wt, const std::vector& val, int n, std::vector>& memo) {
              if (n == 0 || W == 0) {
                  return 0;
              }
              if (memo[n][W] != -1) {
                  return memo[n][W];
              }
              if (wt[n - 1] > W) {
                  memo[n][W] = knapsack(W, wt, val, n - 1, memo);
              } else {
                  memo[n][W] = std::max(val[n - 1] + knapsack(W - wt[n - 1], wt, val, n - 1, memo), knapsack(W, wt, val, n - 1, memo));
              }
              return memo[n][W];
          }
          
          int main() {
              int W = 50;
              std::vector wt = {10, 20, 30};
              std::vector val = {60, 100, 120};
              int n = wt.size();
              std::vector> memo(n + 1, std::vector(W + 1, -1));
              std::cout << "Maximum value in Knapsack = " << knapsack(W, wt, val, n, memo) << std::endl;
              return 0;
          }
      

Bottom-Up Approach (Tabulation)

        #include 
          #include 
          
          int knapsack(int W, const std::vector& wt, const std::vector& val) {
              int n = wt.size();
              std::vector> dp(n + 1, std::vector(W + 1, 0));
          
              for (int i = 1; i <= n; ++i) {
                  for (int w = 1; w <= W; ++w) {
                      if (wt[i - 1] <= w) {
                          dp[i][w] = std::max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                      } else {
                          dp[i][w] = dp[i - 1][w];
                      }
                  }
              }
              return dp[n][W];
          }
          
          int main() {
              int W = 50;
              std::vector wt = {10, 20, 30};
              std::vector val = {60, 100, 120};
              std::cout << "Maximum value in Knapsack = " << knapsack(W, wt, val) << std::endl;
              return 0;
          }
      

Example 4: Coin Change Problem

Top-Down Approach (Memoization)

        #include 
          #include 
          #include 
          
          int coinChange(const std::vector& coins, int amount, std::vector& memo) {
              if (amount == 0) {
                  return 0;
              }
              if (memo[amount] != -1) {
                  return memo[amount];
              }
              int minCoins = INT_MAX;
              for (int coin : coins) {
                  if (amount - coin >= 0) {
                      int res = coinChange(coins, amount - coin, memo);
                      if (res != INT_MAX) {
                          minCoins = std::min(minCoins, res + 1);
                      }
                  }
              }
              memo[amount] = (minCoins == INT_MAX) ? -1 : minCoins;
              return memo[amount];
          }
          
          int main() {
              std::vector coins = {1, 2, 5};
              int amount = 11;
              std::vector memo(amount + 1, -1);
              int result = coinChange(coins, amount, memo);
              if (result == -1) {
                  std::cout << "Cannot make up the amount with the given coins." << std::endl;
              } else {
                  std::cout << "Fewest number of coins to make up the amount: " << result << std::endl;
              }
              return 0;
          }
      

Bottom-Up Approach (Tabulation)

        #include 
          #include 
          #include 
          
          int coinChange(const std::vector& coins, int amount) {
              std::vector dp(amount + 1, amount + 1);
              dp[0] = 0;
          
              for (int i = 1; i <= amount; ++i) {
                  for (int coin : coins) {
                      if (i - coin >= 0) {
                          dp[i] = std::min(dp[i], dp[i - coin] + 1);
                      }
                  }
              }
              return dp[amount] > amount ? -1 : dp[amount];
          }
          
          int main() {
              std::vector coins = {1, 2, 5};
              int amount = 11;
              int result = coinChange(coins, amount);
              if (result == -1) {
                  std::cout << "Cannot make up the amount with the given coins." << std::endl;
              } else {
                  std::cout << "Fewest number of coins to make up the amount: " << result << std::endl;
              }
              return 0;
          }
      

Example 5: Edit Distance (Levenshtein Distance)

Top-Down Approach (Memoization)

        #include 
          #include 
          #include 
          
          int minDistance(const std::string& word1, const std::string& word2, int i, int j, std::vector>& memo) {
              if (i == 0) {
                  return j;
              }
              if (j == 0) {
                  return i;
              }
              if (memo[i][j] != -1) {
                  return memo[i][j];
              }
              if (word1[i - 1] == word2[j - 1]) {
                  memo[i][j] = minDistance(word1, word2, i - 1, j - 1, memo);
              } else {
                  int insert = minDistance(word1, word2, i, j - 1, memo);
                  int remove = minDistance(word1, word2, i - 1, j, memo);
                  int replace = minDistance(word1, word2, i - 1, j - 1, memo);
                  memo[i][j] = 1 + std::min({insert, remove, replace});
              }
              return memo[i][j];
          }
          
          int main() {
              std::string word1 = "horse";
              std::string word2 = "ros";
              int m = word1.size();
              int n = word2.size();
              std::vector> memo(m + 1, std::vector(n + 1, -1));
              std::cout << "Minimum edit distance is " << minDistance(word1, word2, m, n, memo) << std::endl;
              return 0;
          }
      

Bottom-Up Approach (Tabulation)

        #include 
          #include 
          #include 
          #include 
          
          int minDistance(const std::string& word1, const std::string& word2) {
              int m = word1.size();
              int n = word2.size();
              std::vector> dp(m + 1, std::vector(n + 1));
          
              for (int i = 0; i <= m; ++i) {
                  for (int j = 0; j <= n; ++j) {
                      if (i == 0) {
                          dp[i][j] = j;
                      } else if (j == 0) {
                          dp[i][j] = i;
                      } else if (word1[i - 1] == word2[j - 1]) {
                          dp[i][j] = dp[i - 1][j - 1];
                      } else {
                          dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
                      }
                  }
              }
              return dp[m][n];
          }
          
          int main() {
              std::string word1 = "horse";
              std::string word2 = "ros";
              std::cout << "Minimum edit distance is " << minDistance(word1, word2) << std::endl;
              return 0;
          }
      

---

Next >