DP Quick Kit: quick revision, 16 bites

DP શું છે?

ઑપ્ટિમાઇઝ્ડ રિકર્ઝન.

**Dynamic Programming (DP)** એક ઑપ્ટિમાઇઝેશન ટેકનિક છે. તે **ઓવરલેપિંગ સબપ્રોબ્લેમ્સ** અને **ઑપ્ટિમલ સબસ્ટ્રક્ચર** ધરાવતી સમસ્યાઓને ઉકેલે છે. તે ઇન્ટરમીડિયેટ પરિણામોને સ્ટોર કરીને બિનજરૂરી ગણતરીઓ ટાળે છે. આને કારણે DP ને **ઑપ્ટિમાઇઝ્ડ રિકર્ઝન** પણ કહેવાય છે.

Takeaway. DP એ રિકર્ઝનમાં બિનજરૂરી ગણતરીઓ ટાળવાની ટેકનિક છે.

ફિબોનાકી: DP નું ક્લાસિક ઉદાહરણ

ફિબોનાકી DP કેવી રીતે કામ કરે છે?

ફિબોનાકી સિક્વન્સમાં દરેક સંખ્યા પાછલી બે સંખ્યાઓનો સરવાળો હોય છે. રિકર્ઝનનો ઉપયોગ કરતાં સમય જટિલતા $O(2^n)$ થાય છે. DP આને **લીનિયર** $O(n)$ માં ફેરવે છે.

Takeaway. DP ફિબોનાકીને એક્સપોનેન્શિયલથી લીનિયર સમયમાં ઑપ્ટિમાઇઝ કરે છે.

DP ની બે મુખ્ય પ્રોપર્ટીઝ

DP ક્યારે લાગુ કરવું?

Takeaway. DP ફક્ત એવી સમસ્યાઓ માટે જ ઉપયોગી છે જે આ બંને ગુણધર્મો ધરાવે છે.

મેમોઇઝેશન વિ. ટેબ્યુલેશન

બે DP અભિગમોની સરખામણી.

Takeaway. શરૂઆતમાં મેમોઇઝેશન સરળ લાગે છે, પરંતુ લાંબા ગાળે ટેબ્યુલેશન વધુ સારું છે.

ટેબ્યુલેશનના 3 પગલાં

ટેબ્યુલેશન કેવી રીતે લખવું?

Takeaway. ટેબ્યુલેશનમાં હંમેશા નાની સમસ્યાથી શરૂ કરીને મોટી તરફ જવાનું હોય છે.

ફિબોનાકી: ટેબ્યુલેશન કોડ (C++)

C++ માં ટેબ્યુલેશન કોડ.

Takeaway. આ કોડ ફિબોનાકીને $O(n)$ સમય અને $O(n)$ સ્પેસમાં ઉકેલે છે.

ફિબોનાકી: મેમોઇઝેશન કોડ (C++)

C++ માં મેમોઇઝેશન કોડ.

Takeaway. મેમોઇઝેશન રિકર્ઝનમાં સ્ટોરેજ ઉમેરીને ગણતરીઓ ટાળે છે.

DP દરેક રિકર્ઝન પર લાગુ નથી પડતું

બધા રિકર્ઝન DP નથી હોતા.

દા.ત., પ્રથમ n પ્રાકૃતિક સંખ્યાઓનો સરવાળો કાઢવા માટે રિકર્ઝનનો ઉપયોગ કરી શકાય છે, પરંતુ તેમાં **ઓવરલેપિંગ સબપ્રોબ્લેમ્સ** નથી. દરેક કૉલ ફક્ત એક જ વાર થાય છે, તેથી DP તેના પર લાગુ પડતું નથી.

Takeaway. DP લાગુ કરતા પહેલા ઓવરલેપિંગ સબપ્રોબ્લેમ્સ છે કે કેમ તે તપાસો.

DP નો વાસ્તવિક ઉપયોગ

DP નો ઉપયોગ ક્યાં થાય છે?

Google, Amazon, Microsoft જેવી કંપનીઓ ઇન્ટરવ્યુમાં DP પર આધારિત પ્રશ્નો પૂછે છે. તેનો ઉપયોગ રૂટીંગ, શેડ્યુલિંગ, સંસાધન ફાળવણી, અને બાયોઇન્ફોર્મેટિક્સ (દા.ત., DNA સિક્વન્સ એલાઇનમેન્ટ) જેવા ક્ષેત્રોમાં થાય છે.

Takeaway. DP એ પ્લેસમેન્ટ અને ઇન્ટરવ્યુ માટે અત્યંત મહત્વપૂર્ણ વિષય છે.

DP પેટર્ન્સનું મહત્વ

પેટર્ન્સ ઓળખો, સમસ્યાઓ ઉકેલો.

DP ને સમજવાની શ્રેષ્ઠ રીત **પેટર્ન્સ** ઓળખવાની છે. દરેક પેટર્ન (દા.ત., 1D DP, Knapsack, LCS) નો કોર લોજિક સમજી લેવાથી તેના પર આધારિત 10-12 સંબંધિત પ્રશ્નો સરળતાથી ઉકેલી શકાય છે.

Takeaway. DP પેટર્ન્સ ઓળખવાથી તમે મોટી સંખ્યામાં પ્રશ્નો ઉકેલી શકો છો.

ઓનલાઇન અસેસમેન્ટમાં ટેબ્યુલેશન પસંદ કરો

OA માં ટેબ્યુલેશન વધુ સારું.

ઓનલાઇન અસેસમેન્ટ (OA) માં **ટેબ્યુલેશન** ને વધુ પ્રાધાન્ય આપો. તે રિકર્ઝનના ઓવરહેડ અને સ્ટેક ઓવરફ્લોની સમસ્યાને ટાળે છે. જોકે, ગ્રાફ પર DP માટે મેમોઇઝેશન વધુ સારું રહે છે કારણ કે તે ફક્ત રીચેબલ સ્ટેટ્સની જ ગણતરી કરે છે.

Takeaway. OA માટે ટેબ્યુલેશન અને ગ્રાફ DP માટે મેમોઇઝેશન પસંદ કરો.

DP નો ઇતિહાસ

DP શબ્દ ક્યાંથી આવ્યો?

**Dynamic Programming** શબ્દ 1950ના દાયકામાં રિચાર્ડ બેલમેને આપ્યો હતો. તે સમયે 'programming' શબ્દનો અર્થ ઑપ્ટિમાઇઝેશન સમસ્યાઓ ઉકેલવાની પદ્ધતિ હતો, કોમ્પ્યુટર કોડ લખવાનો નહીં.

Takeaway. DP શબ્દનો ઉદ્દભવ ઑપ્ટિમાઇઝેશન થિયરીમાંથી થયો છે.

DP યાદ રાખવાની ટ્રિક

DP = યાદ રાખો + ફરી ઉપયોગ કરો.

DP ને યાદ રાખવાની સરળ રીત: **'ડુ પ્લીઝ'** (Do Please) - **ડુ** (Do) એટલે ગણતરી કરો, અને **પ્લીઝ** (Please) એટલે પરિણામને સ્ટોર કરો જેથી ફરીથી ગણતરી ન કરવી પડે.

Takeaway. DP = ગણતરી કરો અને સ્ટોર કરો.

મુખ્ય DP પેટર્ન્સની યાદી

આ પેટર્ન્સ પર ધ્યાન આપો.

Takeaway. આ પેટર્ન્સમાં નિપુણતા મેળવવાથી 80-85% DP પ્રશ્નો ઉકેલી શકાય છે.

DP શીખવાની વર્કફ્લો

DP માસ્ટર બનવાનો રોડમેપ.

Takeaway. DP માસ્ટર બનવા માટે પેટર્ન સમજો, ક્લાસિક ઉકેલો અને પ્રેક્ટિસ કરો.

DP નું સરળ ઉદાહરણ

DP = નોંધપોથી રાખવી.

કલ્પના કરો કે તમારે વારંવાર એક જ ગણિતનો સવાલ ઉકેલવો પડે છે. શું તમે દર વખતે ફરીથી ગણતરી કરશો કે જવાબ એક નોટબુકમાં લખીને ફરીથી ઉપયોગ કરશો? DP બરાબર આ જ કરે છે - તે પરિણામોને 'નોટબુક' (એરે) માં સ્ટોર કરે છે.

Takeaway. DP એ ગણતરીઓને યાદ રાખીને ફરીથી ઉપયોગ કરવાની ટેકનિક છે.