Hi Folks,I am learning competitive programming now a days.I have started solving recursion/dp based problems.I am trying this problem link. Please help me to find out recursion in the above problem.

Thanks

Hi Guys , Could you please help me to find out the algorithm for this problem.

NOTE : What I tried ? a:) I tried to think of subset sum variation. b:) I have also tried some sort of sorting + two pointer approach.

But I am not able to find out good running time for this problem.Please help me guys to solve this problem.

Shinchan's mom has asked Shinchan to go to market and buy some groceries for dinner. But wait, she don't know how much they will cost. Being a experienced housewife, she know that the maximum possible cost of these groceries can be C. But she can't say about minimum cost so let it be 1. That is cost of groceries can be any integer between 1 and C, inclusive.

In Kasukabe, Shinchan's land, coins are of N denominations. Let these values be V = {v1, v2, ..., vN}. Given these values and C, maximum cost of grocery, help Shinchan in finding minimum number of coins he need to take to market so that he can buy the groceries. He can have any number of coins of any given denomination.

Constraints: 1 <= C <= 10^5 1 <= N <= 10^5 1 <= vi <= 10^5, 0 < i <= N All elements of V are distinct.

Input In first line we have two space separated integer, C N, maximum possible cost of grocery and number of types of coins. In next line there are N space separated integers, values of different types of coins.

Output Print the minimum number of coins Shinchan can take to market so that he can pay any value between 1 and C, inclusive. If it is not possible then print -1. Sample Input (Plaintext Link)

20 4 1 2 5 10

Sample Output (Plaintext Link)

5

How do i solve this Dynamic Programming Problem link