Dynamic Programming

Question 1

what is DP

Answer 1

• enhanced recursion
• recursion is parent of DP

Question 2

how to identify DP problem

Answer 2

• recursion ke identify karne ke jo tarike he wahi tarike DP ko identify karne ke liye bhi use honge
• DP me optimal solution chaiye hota he
• ## agar hamare pas choice hoga, to wo DP ka problem hoga

Question 3

Questions involve in DP

Answer 3

0-1 knapsack
unbounded knapsack
fibonachi
LCS
LIS - longest increasing subsequence
kadanes algo
matrix chain multi
DP on trees
DP on grid
others

Question 4

explain 0/1 knapsack problem

Question 5

7. Explain what is subset sum problem

Question 6

8. explain equal sum partition problem

Answer 6

-

Question 7

9. explain count of subsets sum with given sum

Answer 7

• number of subsets find karyche, kiti ahe jyanchi sum given sum shi match hoti
• ## return zero, if no subsets

Question 8

10. minimum subset sum difference

Answer 8

• ek array dilela ahe
  tyala two arrays made partition karyche
• suppose P1 and P2
• donhi partition chi sum kadychi, sum1 and sum2
• ani sum1 - sum2 minimum aala pahije
• ## larger number madun chota sum minus karycha

Question 9

11. count the number of subset with a given difference

Answer 9

-

Question 10

12. Explain what is Target Sum Problem

Answer 10

• ek sum dilel asel
• pratek array element samor sign dyachi, + kiva
• ani signs ashya prakere assign kryche ahe ki, ji sum dileli ahe, ti sum aali pahije
• ## pratek element samor sign den compulsary ahe

Question 12

signs dilyane kay hot ahe

Answer 12

• signs dilya ne, to given array don subsets mde divide houn zato
• ek positive int cha array
• ek negative int cha array
• ## ani aapan tya don sub arrays la minus kartoy

Question 13

Is Target sum problem same as count subset with given difference

Question 14

what are three types of knapsack

Answer 14

1. fractional knapsack
2. 0 1 knapsack
3. unbound knapsack

Question 15

what is difference between this three types of knapsack

Answer 15

0 1 - knapsack
- elements la completely include karu shakto kiva include nahi karu shakat

01 knapsack made aapan ekada decide karto ki particular item la include karycha ahe ki nahi, nantr aapan tyala sodun deto

unbound knapsack

unbound knapsack mde aapan eka element la analyse kel ki yala select kryache ka nahi mag aapan parat tya element la visit karun select kiva non-select karu shakto

unbound knapsack allows multiple occurences of same item

Question 16

which problems are variations of unbound knapsack

Answer 16

3. 4.

Question 17

code of 01 knapsack

Answer 17

if( wt[ i-1 ] <= j )
max( val[ i - 1 ] + t[ i - 1 ] )

Question 18

code of unbound knapsack problem

Question 19

14 explain rod cutting problem

Answer 19

ek rod dileli aste, tyachi ek length dileli aste

Question 20

15. Explain problem statement of Coin change problem: max number of ways

Question 21

16 Coin change problem: Minimum number of coins

Question 22

17 Coin change problem Contd.

Question 23

18 Longest common subsequence Introduction

List variations of LCS

Answer 23

longest common substring
print LC substring
shortest common substring
print SCS
minimum no of insertion and deletions
largest repeating subsequence
length of longest subsequence of a which is a substring is b