Coding Club Of Competitive Programmers

Subset Sum using Dynamic Programming DP Tutorial 3 Prerequisite – Tutorial 1 , Tutorial 2 Problem Statement- Given a array of integer you have to tell if there is subset present in array which have the sum equal to given array. Eg.arr[]=[2,3,7,8,10]      Sum=11 Output -Yes Sumset={3,8} Parent Problem - 0-1    knapsack how it is related to 0-1 knapsack? I want to tell again that we try to drive solution of child problem from parent problem.In this problem we can choose a element or not and any where if this type of pattern trigger then surely that problem can be solved using 0-1 knapsack pattern.And as we forward in tutorial you can easily find. Choice diagram of subset sum Choice diagram of 0-1 knapsack How to identify Dynamic Programming - 1.choice – In this problem you can choose a element or not.Condition 1 is satisfied. 2.Optimal- In this problem you can’t see the maximum or minimum don’t worry now assign 1 to yes a...

Tutorial 0 Introduction to dynamic programming- Agenda. 1.what is dynamic programming? 2.Type of dynamic programming 3.How to identify dynamic programming problem 4.parents problem of dynamic programming   1.Dynamic Programming or DP ?- DP is a problem solving technique which can be divided into similar sub problem for more details https://en.wikipedia.org/wiki/Dynamic_programming   Lets understand through an example - There is a famous problem name as minimum coin change in this problem you have infinite supply of coins and you have to tell minimum coin change for x. Coins=[1,5,6,9] X=11 Now understand the concept of similar sub problem Amount 0 1 2 3 4 5 6 7 8 9 10 11 Minimum coin change 0 1 2 3 4 1 1 2 3 1 2 2...