DP Quick Kit: 19 MCQs with answers

Recursion

DP ને ઓપ્ટિમાઇઝ્ડ Recursion કહેવામાં આવે છે કારણ કે તે રિકર્સિવ સોલ્યુશનમાં રિડન્ડન્ટ કમ્પ્યુટેશનને ટાળે છે.

$O(2^n)$

Fibonacci માટે સાદા રિકર્સિવ સોલ્યુશનની ટાઇમ કોમ્પ્લેક્સિટી $O(2^n)$ છે કારણ કે ઘણા સબપ્રોબ્લેમ્સ વારંવાર કમ્પ્યુટ થાય છે.

Bottom-Up Approach

Tabulation ને Bottom-Up Approach કહેવામાં આવે છે કારણ કે તે સૌથી નાના Subproblem થી શરૂ કરીને મોટા તરફ જાય છે.

True

DP લાગુ કરવા માટે Overlapping Subproblems અને Optimal Substructure બંને જરૂરી છે.

False

Memoized DP સોલ્યુશનની ટાઇમ કોમ્પ્લેક્સિટી $O(n)$ છે, કારણ કે દરેક Subproblem માત્ર એક જ વાર કમ્પ્યુટ થાય છે.

False

Tabulation માં Iteration (Loops) નો ઉપયોગ થાય છે, Recursion નો નહીં.

True

Memoization મોટા પ્રોબ્લેમથી શરૂ કરીને નાના તરફ જાય છે, તેથી તેને Top-Down Approach કહેવામાં આવે છે.

Overlapping Subproblems અને Optimal Substructure

DP લાગુ કરવા માટે Overlapping Subproblems અને Optimal Substructure બંને પ્રોપર્ટીઝ હોવી જરૂરી છે.

Recursion અને Storage Structure

Memoization માં Recursion સાથે Storage Structure (જેમ કે Array) નો ઉપયોગ થાય છે.

Data Structure ને Define કરવું અને Initialize કરવું

Tabulation માં પહેલા Data Structure (DP Array) ને Define કરી, Initialize કરવામાં આવે છે, પછી Small to Big Solve કરવામાં આવે છે.

$O(n)$

Memoized DP સોલ્યુશનમાં દરેક Subproblem માત્ર એક જ વાર કમ્પ્યુટ થાય છે, તેથી ટાઇમ કોમ્પ્લેક્સિટી $O(n)$ થઈ જાય છે.

Sum of first n natural numbers

Sum of first n natural numbers માં ફક્ત એક જ Recursive Call થાય છે, તેથી Overlapping Subproblems નથી હોતા.

dp[0] = 0, dp[1] = 1

Fibonacci માટે Tabulation માં dp[0] = 0 અને dp[1] = 1 થી Initialize કરવામાં આવે છે.

Memoization Recursion વાપરે છે, Tabulation Loops વાપરે છે

Memoization Recursion સાથે Storage વાપરે છે, જ્યારે Tabulation Iteration (Loops) સાથે Table વાપરે છે.

મોટા પ્રોબ્લેમનો ઓપ્ટિમલ સોલ્યુશન નાના સબપ્રોબ્લેમ્સના ઓપ્ટિમલ સોલ્યુશનથી બનાવી શકાય છે

Optimal Substructure એટલે કે મોટા પ્રોબ્લેમનો ઓપ્ટિમલ સોલ્યુશન તેના સબપ્રોબ્લેમ્સના ઓપ્ટિમલ સોલ્યુશનથી બનાવી શકાય છે.

False

આ પ્રોબ્લેમમાં Overlapping Subproblems નથી, તેથી DP લાગુ કરી શકાતું નથી.

True

Tabulation Recursion ના Stack Overflow અને Overhead ને ટાળે છે, તેથી Online Assessments માં તે વધુ પ્રિફર કરવામાં આવે છે.

False

Tabulation માં DP Array ને Base Values (dp[0]=0, dp[1]=1) થી Initialize કરવામાં આવે છે, -1 થી નહીં.

Binary Search

Binary Search એ DP Pattern નથી, તે Divide and Conquer પર આધારિત છે.