Coin Change Combination

Faq

Q1) why do we create dp array of size n+1 not n?
ans: Since the array indexing start from 0 if we create a array od n size then index will be for 0 to n-1.Therefore we are creating array with size n+1.

Q2) What is the meaning of cells for the dp array?
ans: cells represents the max combination possible of that amount i.e the index.

Q3) In which direction the array will be traverse?
ans: From left to right.

Q4) Where will be the answer present?
ans: The answer will be the present at the last index.

Hints

Hint 1: Use the concept of target sum pair Problem.

Hint 2: Make a storage array of size n+1.

Hint 3: Iterate through the array and storage the max combination in each index where the index is the target.

Hint 4: The final is to be store in the last index i.e n index int the storage array.

Mcq

Q1) What will be the size of the storage array for the given array of size n?
 a) n
 b) n-1
 c) n+1
 d) n*n

ans: d)

Q2) what is the meaning of the cell?
  a) same value as in the given array.
  b) cells represents the max combination possible of that amount.
  c) cells represents the min combination possible of that amount.
 
 ans: b)
 
Q3) what will be the value of the first index in storage array?
  a)  dp[0] = 1
  b)  dp[0] = 0
  c)  dp[1] = 2
  d)  dp[0] = -1
 
ans: a)