DP Quick Kit: 17 flashcards

DP એ એક **optimization technique** છે જે **overlapping subproblems** અને **optimal substructure** ધરાવતી સમસ્યાઓને ઉકેલે છે. તે **intermediate results** ને store કરીને redundant computations ટાળે છે.

કારણ કે ઘણી recursive સમસ્યાઓની time complexity **exponential** ($O(2^n)$) હોય છે, અને DP તેને optimize કરીને **linear** ($O(n)$) બનાવી શકે છે.

$$f(n) = f(n-1) + f(n-2)$$ જ્યાં $f(0) = 0$ અને $f(1) = 1$.

Time complexity **$O(2^n)$** છે. કારણ કે recursion tree માં ઘણા subproblems (જેમ કે $f(2)$, $f(3)$) **વારંવાર recalculate** થાય છે.

આમાં **recursion** નો ઉપયોગ થાય છે અને intermediate results store કરવા માટે **array/vector** જેવું data structure લેવાય છે. શરૂઆતમાં array ને $-1$ (અથવા કોઈ sentinel value) વડે initialize કરવામાં આવે છે. Recursive call કરતા પહેલા check કરાય છે કે શું value પહેલેથી calculate થઈ ગઈ છે (i.e., $-1$ નથી). જો હા, તો stored v…

Time complexity **$O(n)$** (linear) થઈ જાય છે. કારણ કે દરેક subproblem (જેમ કે $f(2), f(3), ...$) **માત્ર એક જ વાર** calculate થાય છે અને પછી store થઈ જાય છે, જેનો reuse થાય છે.

1. **Overlapping Subproblems**: સમસ્યાને એવા નાના ભાગોમાં વિભાજિત કરી શકાય જેનો **વારંવાર ઉપયોગ** થાય. 2. **Optimal Substructure**: મોટી સમસ્યાનો **optimal solution** તેના નાના ભાગોના optimal solutions ને જોડીને બનાવી શકાય.

**ના**, લાગુ થઈ શકતું નથી. કારણ કે તેમાં **optimal substructure** છે (sum(n) = n + sum(n-1)), પરંતુ **overlapping subproblems** નથી. દરેક recursive call માત્ર **એક જ** નવી call કરે છે, તેથી કોઈ subproblem નું પુનરાવર્તન થતું નથી.

આમાં **iteration (loops)** નો ઉપયોગ થાય છે અને **table (array)** માં results store થાય છે. પ્રક્રિયા: 1. **Define data structure**: array `dp` બનાવો, જ્યાં `dp[i]` નો અર્થ નક્કી કરો (દા.ત., Fibonacci માટે `dp[i]` = $i$મો Fibonacci નંબર). 2. **Initialize**: સૌથી નાની સમસ્યાઓના solutions વડે array ભરો (દા.ત., `dp[0]=0`,…

**Memoization (Top-Down)**: સૌથી મોટી સમસ્યા (દા.ત., $f(n)$) થી શરૂ કરી, recursion દ્વારા નાની સમસ્યાઓ (દા.ત., $f(n-1), f(n-2)$) તરફ જાય છે. **Tabulation (Bottom-Up)**: સૌથી નાની સમસ્યાઓ (દા.ત., $f(0), f(1)$) થી શરૂ કરી, loop દ્વારા મોટી સમસ્યાઓ (દા.ત., $f(n)$) તરફ જાય છે.

1. **Stack Overflow ટાળે છે**: Memoization recursion નો ઉપયોગ કરે છે, જે ઘણી deep calls માં stack overflow લાવી શકે છે. Tabulation માં આ સમસ્યા નથી. 2. **Overhead ઓછો**: Recursion નો વધારાનો stack overhead નથી. 3. **વધુ કાર્યક્ષમ**: ઘણી વખત Tabulation વધુ સીધો અને ઝડપી હોય છે.

**DP on Graphs** જેવી સમસ્યાઓમાં, જ્યાં **invalid states** ની ગણતરી ટાળવી હોય ત્યાં Memoization વધુ સારો વિકલ્પ છે. Tabulation બધી જ possible states માટે ગણતરી કરે છે, જ્યારે Memoization માત્ર **reachable states** માટે જ ગણતરી કરે છે.

**ઉદાહરણ**: Fibonacci sequence. **સંબંધિત પ્રશ્નો**: Climbing Stairs, House Thief, Frog Jump, Minimum Jumps.

**ઉદાહરણ**: 0/1 Knapsack. **સંબંધિત પ્રશ્નો**: Rod Cutting, Subset Sum.

**ઉદાહરણ**: Longest Common Subsequence. **સંબંધિત પ્રશ્નો**: Longest Increasing Subsequence (LIS), Edit Distance.

**ઉદાહરણ**: Matrix Chain Multiplication. **સંબંધિત પ્રશ્નો**: Palindrome Partitioning, Boolean Parenthesization.

એક pattern ની **core logic** સમજી લીધા પછી, તે જ pattern પર આધારિત **8-10 સંબંધિત પ્રશ્નો** સરળતાથી ઉકેલી શકાય છે. આ રીતે 70-80% DP પ્રશ્નો કવર થઈ જાય છે.