The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# Solution: **Dynamic Programming approach**

Since the same subproblems are computed again and again, this problem has the *overlapping subproblems* property.

Like other typical dynamic programming problems, re-computations of the same subproblems can be avoided by constructing a temporary array `dp[]` and memoizing the computed values in that array.

#include <bits/stdc++.h>
using namespace std;

int coins[] = {1,2,3,4,5}; 
int dp [1000] = {0};
int minCoins(int N, int M)
{
  //Initializing all values to INT_MAX i.e. minimum coins to make any
  //amount of sum is INT_MAX
  for(int i = 0;i<=N;i++)
    dp[i] = INT_MAX;
  
  //Base case 
  //Minimum coins to make sum = 0 cents is 0
  dp[0] = 0;
  
  //Iterating in the outer loop for possible values of sum between 1 to N
  //Since our final solution for sum = N might depend upon any of these values
  for(int i = 1;i<=N;i++)
  {
    //Inner loop denotes the index of coin array.
    //For each value of sum, to obtain the optimal solution.
    for(int j = 0;j<M;j++)
    {
      //i —> sum
      //j —> next coin index
      //If we can include this coin in our solution
      if(coins[j] <= i)
      {
        //Solution might include the newly included coin
        dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
      }
    }
  }
  return dp[N];
}

int main() {
  // your code goes here
  int sum = 50;
  int total_coins = 5;
  cout << minCoins(sum, total_coins);
}

**Explanation:**
* The explanation is given in the comments section of the code.

So that's the dynamic programming approach. We used tabulation, saved the solution of the subproblems, and then returned the optimal solution. 

The complexity is $O(M*N)$ in this solution, where $M$ is the number of coins and $N$ is the change required. You can see that because of memoization, we get the output pretty fast, even with a higher value of `sum`.

The approach we discussed here is bottom-up. As an exercise, try to implement one more solution that uses the top-down dynamic programming approach. 


Implement an optimized solution for the problem discussed in the previous lesson.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Minimum Coin Change Problem - Solution Using DP

Solution: Dynamic Programming approach