104 - Little shop of flowers

لینک سوال

مفهوم سوال

تو این سوال باید ویترین یک گل فروشی رو طوری بچینیم که بیشترین زیبایی ممکن رو داشته باشه .

ویترین مغازه شامل F طبقه ( سطر ) و هر طبقه شامل V گلدانه .

گلدانها به طبقه چسبیده شدند ! همچنین هر گلدان حداکثر 1 دسته گل رو می تونه تو خودش جا بده .

F تا دسته گل داریم که به ترتیب از 1 , ... , F شماره گذاری شده اند .

سوال از ما می خواد طوری گلهارو بچینیم که گل شماره i سمت سمت چپ گل شماره j باشه . ( i < j )

سوال به ما میزان زیبایی هر گلدان رو میده و ماکزیمم زیبایی ممکن و چینش نهایی رو از ما می خواد .

F , V < 100

حل

Lowest Common Ancestor

در یک درخت ریشه دار ، "پایین ترین جد مشترک" دو گره را دورترین راس از ریشه تعریف می کنیم که جد هردو گره باشد .

این مساله معمولا برای درخت های بزرگ مثلا 10⁵ راسی مطرح میشود .

برای حساب کردن ( LCA( x , y به صورت زیر عمل می کنیم .

بدون کاسته شدن از کلیت فرض کنید گره x در ارتفاع بیشتری باشه .

قبل از هر کاری باید گره x رو اونقدر به بالا منتقل کنیم تا هم ارتفاع با y بشه .

حالا اگر x = y باشه در نتیجه LCA همان x است

اگر x != y باشه ، تو این حالت از اونجاییکه فاصله x تا LCA و فاصله y تا LCA برابر است یک مقدار i دلخواه پیدا می کنیم که i امین پدر x و y با هم برابر نباشند ، از اونجایی که 

LCA( x , y ) = LCA( Parent( x , i ) , Parent( y , i ) )

می تونیم قرار بدیم ( x = Parent( x , i ) , y = Parent( y , i و مساله رو برای این زیر مساله حل کنیم .

اگر خوب دقت کنید میبینید که انتخاب i خیلی تو سرعت الگوریتم تاثیر داره .

منظور از ( Parent( x , y یعنی پدر y ام گره x .

ایده کلی ساختمان داده اینه که برای هر گره ، 2⁰ امین پدر ، 2¹ امین پدر ، 2² امین پدر و ... رو نگه داریم .

حالا برای بدست آوردن k امین پدر یک گره کافیه k رو به صورت باینری نگاه کنیم .

از اونجایی که k = 2ⁱ₁ + 2ⁱ₂ + ... + 2ⁱ_n  می تونیم

اول 2ⁱ₁ امین پدر k رو محاسبه کنیم سپس پدر k - 2ⁱ₁ گره جدید رو محاسبه کنیم .

از اونجایی که یه عدد رو میشه به صورت حداکثر Log N تا جمعوند نوشت ، الگوریتم بعد از Log N محاسبه به جواب می رسه .

نحوه ساختن درخت

برای ساختن درخت کافیه برای هر گره بدونید پدرش کیه و تو چه ارتفاعی قرار داره .

برای این کار می تونید درخت از ریشه BFS یا DFS بزنید تا Dep و Parent هر گره رو معلوم کنید .

حالا با داشتن این مقادیر درخت رو می سازیم

for( int i = 0 ; i < N ; i ++ )
    for( int j = 0 ; ( 1 << j ) < N ; j ++ )
        Tree[i][j] = -1;
for( int i = 0 ; i < N ; i ++ )
    Tree[i][0] = Par[i];
for( int j = 1 ; ( 1 << j ) < N ; j ++ )
    for( int i = 0 ; i < N ; i ++ )
        Tree[i][j] = Tree[ Tree[i][j-1] ][j-1];

تو این درخت ، منظور از [Tree[i][j یعنی پدر 2^j ام از گره i .

اول پدر همه رو -1 می زاریم ، یعنی اینکه هیچ پدری نداره .
بعد پدر سطح 2⁰ ام رو مشخص می کنیم .

حالا چون به ترتیب از پایین به بالا حرکت می کنیم ، برای برست آوردن پدر 2^j ام از راس i کافیه ،

پدر 2^j-1 از راس i رو بدست بیاریم ( قبلا محاسبه کردیم و تو خونه [Tree[i][j-1 ذخیره کردیمش ) و بعد پدر 2^j-1 ام اون گره رو بدست بیاریم ( این مقدار رو هم قبلا محاسبه کردیم )

برای بدست آوردن LCA دو گره کافیه تابع زیر رو فراخوانی کنیم

int LCA( int x , int y ) {
  if( Dep[x] < Dep[y] )
    swap( x , y );
  int log = 0;
  for( int log = 0 ; ( 1 << log ) < Dep[x] ; log ++ );
  log --;
  for( int j = log ; j >= 0 ; j -- )
    if( ( Dep[x] - Dep[y] ) & ( 1 << j ) )
      x = Tree[x][j];
  if( x == y )
    return x;
  for( int j = log ; j >= 0 ; j -- )
    if( Tree[x][j] != -1 && Tree[x][j] != Tree[y][j] )
      x = Tree[x][j], y = Tree[y][j];
  return Par[x];
}

پیچیدگی زمانی:

( O( N * Log N برای پیش محاسبات و ساختن درخت

( O( Log N برای بدست آوردن هر Query

حافظه : ( O( N * Log N 

CodeForces Round #236 Div.1 & Div.2

سوال Div2 A. Nuts

سوال میگه یه نفر می خواد a تا آیتم رو توی یه سری جعبه بزاره که تو هر قسمت از جعبه حداکثر v تا آیتم باشه .

در شروع کار طرف b تا divisor ( جداکننده ) داره . اگر در جعبه ای x جداکننده بزاره ، جعبه به x+1

قسمت تقسیم میشه . (تو حالت اولیه فرض میشه که جعبه 1 قسمت داره )

تو هر جعبه حداکثر میشه k تا جداکننده گذاشت .

سوال به ما مقادیر k , a , b , v رو میده و کمترین تعداد جعبه هایی که لازمه تا همه آیتم هارو توش قرار بدیم رو می خواد .

k , a , b , v < 1000

سوال Div2 B. Trees in a Row

سوال به ما یه دنباله از اعداد به طول N میده و میگه می خوایم تبدیلش کنیم به یه تصاعد حسابی با قدرنسبت K تبدیل کنیم .

تو هر لحظه می تونیم یک عدد رو به هر اندازه ای کاهش یا افزایش بدیم ( بعد از انجام عمل باید عدد مثبت باقی بمونه )

سوال از ما کمترین تعداد عمل لازم برای تبدیل دنباله به تصاعد رو می خواد .

N , K , a_i < 1000

سوال Div1 A & Div2 C. Searching for Graph

یک گراف با n راس رو p-interesting میگیم اگر

1. دقیقا p+2*n یال داشته باشه

2. گراف طوقه و یال موازی نداشته باشه

3. به ازای هر زیر گراف با k راس از گراف ، زیرگراف حاصله حداکثر p+2*k یال داشته باشه

سوال به ما عددهای n , p رو میده و از ما می خواد یه گراف با شرایط فوق تولید و چاپ کنیم .

سوال Div1 B & Div2 D. Upgrading Array

یه دنباله N عضوی داریم .

برای یه دنباله تابع f رو به این صورت تعریف می کنیم .

f( a₁ , ... , a_n ) = SUM( f( a_i ) )

f( a_i ) = تعداد عوامل اول خوب - تعداد عوامل اول بد

سوال به ما یه لیست از اعداد اول بد میده ؛ بقیه خوب فرض میشن .

علاوه براین سوال به ما یه عمل معرفی می کنه که می تونیم ازش بی نهایت بار استفاده کنیم .

تو هر بار اندیسی مثل i رو انتخاب می کنیم و i عضو اول دنباله رو به ( GCD( a₁ , ... , a_i تقسیم می کنیم .

سوال از ما بیشترین مقدار ممکن برای تابع f رو می خواد .

N < 5000

سوال Div1 C & Div2 E. Strictly Positive Matrix

سوال به ما یه ماتریس n*n به درایه های نامنفی میده و می خواد ببینه که آیا عددی مثل k وجود داره که توان k ام از ماتریس درایه هایی تماما مثبت داشته باشه ؟

n < 2000

سوال Div1 D. Beautiful Pairs of Numbers

سوال از ما تعداد دنباله های k عضوی از جفت ها رو می خواد که

1. 1 <= a₁ <= b₁ < a₂ <= b₂ < ... < a_k <= b_k <= n

2. b_i - a_i ها همگی متمایز باشند

سوال به ما t تست میده تا پردازش کنیم .

تو هر تست n , k رو میده و تعداد دنباله رو می خواد .

t < 2 * 105 و n , k < 1000

سوال Div1 E. Two Rooted Trees

هنوز حلش نکردم !

حل

CodeForces Round #238 Div.1 & Div.2

سوال A. Gravity Flip

سوال می گفت یه نفر یه جعبه طراحی کرده که میشه توش جاذبه رو از بالا به پایین به چپ به راست تغییر داد .

یه نفر میاد n ستون مربع رو توی این جعبه می زاره و جاذبه رو تغییر میده .

به عنوان خروجی وضعیت نهایی مربع هارو از ما می خواست .

n < 100

سوال B. Domino Effect

سوال می گفت یه نفر n تا دومینو روی زمین می چینه . بعد میاد به یه سری از اونهارو یه ضربه می زنه تا شروع به افتادن کنن . هر ضربه ممکنه به طرف چپ باشه یا طرف راست .

تو هر ثانیه هر دومینوی در حال افتادن به سمت مورد نظر میوفته و دومینوی کناری رو تحت تاثیر خودش قرار میده .

سوال از ما تعداد دومینو هایی رو می خواد که نمی افتند .

n < 3000

سوال Div1 A & Div2 C. Unusual Product

سوال می گفت یه ماتریس n*n داریم که درایه هاش فقط می تونن 0 یا 1 باشن .

سوال یه عمل ضرب روی این ماتریس تعریف می کنه که به هر ماتریس یه عدد ( 0 یا 1 ) نسبت میده .

سوال به ما q تا query می داد .

تو هر query یکی از عمل های زیر باید انجام میشد 

1. درایه های یک سطر داده شده flip بشه

2. درایه های یک ستون داده شده flip بشه

3. حاصل ضرب ماتریس تو خروجی چاپ بشه

n < 10³ و q < 10⁶

سوال Div1 B & Div2 D. Toy Sum

سوال یه بازی دونفره ( بین یه نفر و معلمش ) رو معرفی می کرد .

به این صورت که معلم از بین اعداد 1 تا 10⁶ n تا عدد رو انتخاب می کرد .

حالا نوبت شاگرد بود تا m تا عدد از بین 1 تا 10⁶ که تا به حال انتخاب نشدن انتخاب کنه تا تساوی زیر اتفاق بیوفته

اگر اعداد معلم Xi ها باشن و اعداد شاگرد Yi

SUM( Xi - 1 ) = SUM( 106 - Yj )

سوال Div1 C & Div2 E. Graph Cutting

سوال می گفت می خوایم یالهای یک گراف رو یه صورت جفت جفت کنار هم بزاریم به صورتی که

از همه یالها استفاده شده باشه

هر یال فقط در یک جفت اومده باشه

یالهای هر جفت تو یک سر مشترک باشند

n , m < 10⁵

سوال Div1 D. Hill Climbing

سوال می گفت یه سری تپه داریم که روی یک خط قرار دارند و از چپ به راست شماره گذاری شده اند .

از روی قله هر تپه میشه با یه طناب به قله ی تپه ای دیگه رفت اگر

1. شماره قله بزرگتر از شماره قله فعلی باشه

2. از این نقطه بشه قله مقصد رو دید ( هیچ قله دیگه ای روی مسیر نباشه )

3. بین تمام قله هایی که می تونه بره ، همیشه قله با بزرگترین شماره رو انتخاب می کنه .

سوال به ما m تا query می داد تو هر query می گفت 2 نفر روی قله های شماره a و b هستند و می خواست ، کوچکترین شماره قله ای رو بدید که هردو نفر بتونن به اونجا برسند .

به عنوان ورودی محل قرار گیری مرکز تپه روی محور x ها و ارتفاع قله ی اون رو به ما میدن .

همچنین تو هر query دو شماره قله a , b

n , m < 10⁵ . Xi < 10⁷  . Yi < 10¹¹

سوال Div1 E. Hamming Triples

سوال به ما m تا رشته از 0 , 1 میده . به این صورت که هر رشته فقط می تونه به صورت صعودی یا نزولی باشه .

همچنین Hamming Distance رو بین دو رشته ، تعداد اندیس هایی تعریف می کنیم که کاراکتر متناظر اونها با هم فرق داره .

حالا سوال از ما تعداد سه تایی هایی مثل ( a , b , c ) رو می خواد که

( H(a , b ) + H( b , c ) + H( c , a ماکزیمم باشه .

n < 10⁹ , m < 10⁵ 

CodeForces Round #234 Div.2

سوال A. Inna and Choose Options

سوال می گفت یه نفر میاد 12 تا کاراکتر از {X , O} انتخاب می کنه و می خواد این کاراکترهارو به ترتیب توی یه ماتریس به سایز a*b بچینه ؛ تمام سطر های ماتریس باید کامل باشند .

سوال تمام زوج مرتب هایی مثل (a,b) رو می خواد که اگر کاراکترهارو توی ماتریسی به اندازه a*b بچینیم ، یه ستون کاملا شامل X داشته باشه .

سوال B. Inna and New Matrix of Candies

سوال یه بازی رو معرفی می کنه .

این بازی روی یک صفحه مستطیل به ابعاد n و m انجام میشه .

روی هر سطر دقیقا یک کوتوله و یک آبنبات قرار گرفته .

تو هر دور از بازی یه تعداد ( شاید همه ) از سطر هارو انتخاب می کنیم .

تمام کوتوله های روی سطر های انتخاب شده شروع به حرکت به سمت راست می کنن .

تو هر لحظه یک خونه به سمت راست میرن .

اولین زمانیکه یکی از کوتوله ها به یه خونه شامل آبنبات برسه یا اینکه یکی به انتهای سطر خودش برسه ، همه حرکت خودشون رو متوقف می کنن و این دور از بازی تموم میشه .

سوال از ما می خواد کمترین تعداد دور های بازی رو بدست بیاریم یا اینکه بگیم این کار غیر ممکنه .

سوال به عنوان ورودی وضعیت صفحه بازی رو به ما میده . خونه های شامل کوتوله با حرف G و خونه های شامل آبنبات با حرف S و بقیه خونه ها با * مشخص میشن .

n,m < 1000

سوال C. Inna and Huge Candy Matrix

این سوال می گفت یه نفر یه ماتریس بزرگ داشته که روی p سلول از اون آبنبات داره .

یه نفر دیگه میاد این ماتریس رو x بار 90 درجه در جهت عقربه های ساعت دوران میده و بعد از اون y مرتبه اون رو نسبت به محور تقارن عمودی بازتاب می کنه و در آخر اون رو z مرتبه 90 درجه خلاف جهت عقربه های ساعت دوران میده .

ما محل قرارگیری قبل از دوران هارو داریم و محل جدید اونها رو می خوایم .

به عنوان ورودی سایز ماتریس رو داریم n , m < 10^9

همچنین مختصات اولیه p نقطه .

سوال D. Dima and Bacteria

سوال میگه  n تا باکتری داریم که از k نوع مختلف هستند . 

n < 10^5 , k < 500

باکتری هارو با شماره های 1 تا n شماره گذاری کردیم .

باکتری های مشابه شماره های متوالی دارند .

سوال میگه ما یه دستگاه خاص داریم که می تونه انرژی رو از یه باکتری به دیگری منتقل کنه .

در کل سوال به ما m نوع انتقال رو معرفی می کنه به این صورت که از باکتری با شماره u میشه انرژی رو به باکتری شماره v منتقل کرد با هزینه x .

یه توزیع از باکتری رو خوب میگیم اگر بشه انرژی رو بین باکتری های مشابه با هزینه صفر منتقل کرد .

به عنوان خروجی سوال از ما کمترین هزینه برای انتقال انرژی بین باکتری با انواع مختلف رو می خواد ، در صورتی که توزیع انرژی خوب باشه و در غیر این صورت No .

سوال E. Inna and Binary Logic

این سوال میگه از یه لیست شامل n عضو ، n لیست جدید می سازیم که عناطر لیست k ام معادل با انجام عمل AND روی k عضو متوالی از آرایه اولیه است .

یعنی :

A[k][i] = AND( a[i] , a[i+1] , ... , a[i+k-1] )

منظور از AND عمل منطقی ِAND است .

سوال حاصل جمع همه عناصر موجود در همه لیست هارو از ما می خواد .

ُسوال به ما m تا query میده که تو هر کدوم مقدار یکی از اعداد آرایه اصلی تغییر می کنه .

برای هر query باید حاصل جمع جدید رو محاسبه و چاپ کنیم .

n, m , a[i] < 10^5

حل سوالات

کوتاه ترین مسیر

در این مقاله الگوریتم های موجود در زمینه کوتاه ترین مسیر رو به ترتیب معرفی خواهیم کرد .

103 - Traffic Lights

لینک سوال

مفهوم سوال

شهری داریم که از یه سری خیابان و یه سری تقاطع تشکیل شده .

تو هر تقاطع یه چراغ نصب شده که با زمان بندی مشخص آبی و قرمز میشه .

از یک خیابان میشه گذر کرد اگر و تنها اگر چراغ دوسر اون زمان شروع حرکت هم رنگ باشند .

سوال از ما می خواد کوتاه ترین مسیر از نقطه ای به نقطه دیگه رو بدست بیارم .

به عنوان ورودی به ما وضعیت اولیه چراغ ها ( رنگ فعلی ، زمان باقیمونده از دوره فعلی و دوره زمانی هر رنگ از این چراغ ) ، وضعیت خیابان ها ، نقطه شروع و انتهای مسیر رو میده .

به عنوان خروجی اگر مسیری وجود داشت طول کوتاه ترین مسیر و همچنین یک مسیر دلخواه با طول کمینه رو از ما می خواد .

حل

دور و مسیر اویلری

تعاریف :

گراف G را اویلری می گوئیم اگر و فقط اگر همبند باشد و درجه تمام رئوس آن زوج باشد .

گراف G را نیمه اویلری می گوئیم اگر و فقط اگر همبند باشد و حداکثر 2 رأس درجه فرد داشته باشد .

مسیر بسته ای که که از یک رأس شروع شده و از تمامی یال های گراف دقیقا یکبار می گذرد و به نقطه شروع باز می گردد را دور اویلری گوئیم .

مسیری که از یک رأس شروع شده و از تمامی یال های گراف دقیقا یکبار می گذرد و در نقطه ای دیگر متوقف می شود ، مسیر اویلری گوئیم .

برای پیدا کردن دور(مسیر) اویلری در یک راف ، کافیست شرط اویلری بودن رو چک کنیم .

اگر اویلری بود ، کافیه از راسی دلخواه شروع کنیم . اگر نیمه اویلری بود ، از یک رأس درجه فرد شروع می کنیم .

به راحتی میشه دید که تو گراف نیمه اویلری ، مسیر از یک رأس درجه فرد شروع میشه و به رأس فرد دیگه ختم میشه .

برای بدست آوردن دور(مسیر) الگوریتم خطی نسبت به تعداد یالها( (O(E ) وجود داره .

الگوریتم :

با کمک DFS گراف را پیمایش می کنیم . هر بار که از روی یک یال گذشتیم ، یال مورد نظر رو از گراف حذف می کنیم . زمان بازگشت از DFS رأس فعلی رو به مسیر اضافه می کنیم .

نکته : تو گراف اویلری ، تو هر راس نحوه انتخاب یال بعدی مهم نیست .

نکته : تو گراف های نیمه اویلری ، تو هر راس حداکثر 2 بار DFS فراخوانی میشه .

تو بار اول یک مسیر از این رأس به راس درجه فرد دیگه پیدا میشه اما ممکنه تعدادی از یال ها هنوز استفاده نشده باشند . چون یال های استفاده شده رو حذف کردیم ، گراف باقیمونده اویلری است ، لذا با شروع از همین نقطه دور اویلری ای پیدا می کنیم .

به اضافه کردن این دور به ابتدای مسیری که قبلا پیدا کرده بودیم ، یک مسیر اویلری برای گراف پیدا کردیم .

به عنوان مثال اگر در گراف زیر از نقطه 1 شروع کنیم و به رأس 2 بریم ، مسیر اولیه پیدا شده ولی هنوز یال استفاده نشده وجود داره . لذا دوباره از 1 شروع می کنیم و دور اویلری گراف باقیمونده رو پیدا می کنیم و به اول مسیر قبلی اضافه می کنیم .

1 --- 2

| \

|   \

3 --- 4

مسیر اویلری این گراف میشه :

1 3 4 1 2

کد :

int path[N], len = 0;
void DFS( int x )
{
    for( int i = 0 ; i < N ; i ++ )
        if( mat[x][i] > 0 )
        {
            mat[x][i] --;
            mat[i][x] --;
            DFS( i );
        }
    path[ len ++ ] = x;
}

برای بدست آوردن دور(مسیر) کافیه از main تابع رو برای یه نقطه شروع خوب ( رأس دلخواه در گراف اویلری و رأس فرد در گراف نیمه اویلری ) فراخوانی کنید .

بعد از اجرای DFS ، اگر مسیر شامل E|  + 1| رأس بود ، path شامل دور(مسیر) مورد نظر است .

در غیر این صورت گراف ناهمبند است لذا دور(مسیر) اویلری نداریم .

101 - Domino

لینک سوال

مفهوم سوال

سوال یه سری دومینو به ما میده و می خواد همه ی اونها رو طوری پشت سر هم بچینیم که عدد های مجاور در دومینو ها برابر باشه .

دومینو یک قطعه مستطیل شکل با ابعاد 2*1 فرض شده که روش 2 عدد بین 0 تا 6 نوشته شده .

ترتیب و جهت اصلی دومینو هارو داریم . همچنین می تونیم یه دومینو رو برعکس کنیم و بعد ازش استفاده کنیم .

به عنوان خروجی ترتیب و جهت نهایی دومینو ها یا No Solution رو از ما می خواد .

حل :

برنامه نویسی پویا - Dynamic Programming

سلام

DP روشی است که بر دو مبنای ، رابطه بازگشتی و نقطه شروع بنا شده .

این طور که برای حل سعی می کنیم مساله رو به زیر مساله های کوچک تر تقسیم کنیم و بعد از جواب های بدست اومده جواب مساله کلی رو بدست بیارم .

تا اینجای کار هیچ فرقی بین DP و روش "تقسیم و حل ( غلبه )" (Divide & Conquer ) نیست .

اما وجه تمایز این دو رویکرد در اینه که تو مسائل DP جواب زیر مساله هایی که حل کردیم رو نگه می داریم ( معمولا تو یه آرایه ) و بعد تو تکرار های بعدی از این مقادیر استفاده می کنیم ( برای جلوگیری از محاسبه دوباره ) .

برای اینکه این کار ما مفید باشه باید زیر مساله های تکراری داشته باشیم ، وگرنه خود D&C می تونه مساله رو حل کنه .

به عنوان مثال تابع فاکتوریل ( Factorial ) رو در نظر بگیرید .

یه همچنین تابعی میشه :

int Factorial ( int n )

{

    if( n < 2 )

        return 1;

    return n * Factorial( n-1 );

}

تو همین تابع ساده فرض کنید می خوایم 5! رو بدست بیاریم . تمام مقادیر 1! و 2! و 3! و 4! و 5! ساخته میشن و از بین میرن .

حالا اگر دوباره مثلا 6! رو بخوایم حساب کنیم ، دوباره باید همه مقادیر قبلی رو محاسبه کنیم و ...

حالا اگر مقدار 5! که قبلا محاسبه کرده بودیم رو جایی نگه می داشتیم چی ؟

برای محاسبه 6! فقط کافی بود مقداری که قبلا محاسبه کردیم رو استخراج کنیم و جواب رو بدست بیاریم . توجه داشته باشید که با این کار از 4 بار فراخوانی تابع جلوگیری کردیم .

برای مقادیر بزرگتر و مسائل پیچیده تر این کار فوق العاده کمک می کنه .

چجوری این کارو انجام بدیم ؟

تابع رو یکم تغییر می دیم :

int DP[100] = {0};

int Factorial ( int n )

{

    if( n < 2 )

        return 1;

    if( DP[n] != 0 )

        return DP[n];

    return DP[n] = n * Factorial( n-1 );

}

تو این حالت اگر DP[n] = 0 باشه ، یعنی هوز مقدارش رو حساب نکردیم پس مجبوریم تابع رو برای n-1 فراخوانی کنیم .

اگر DP[n] != 0 بود ، یعنی قبلا این تابع فراخوانی شده بوده و مقدارش حساب شده پس کافیه مقدار DP[n] رو برگردونیم . ( تو این حالت از فراخوانی زیرمساله های تکراری جلوگیری کردیم . )

توابع دیگه ای هم هستند که این شرایط رو دارند ، مثل دنباله فیبوناچی ( سعی کنید خودتون بنویسیدش ) 

تو حل مسائل DP باید برای حل تابع بازگشتی ارائه بدید . این توابع یه سری ورودی مستقل دارند و یه سری ورودی وابسته . برای اینکه بین زیر مساله های مختلف تمایز قائل بشیم باید طوری متغیر های مستقل رو انتخاب کنیم که اولا تمامی زیرمسائل رو شامل بشه و ثانیا زیر مساله ها با هم تداخل نداشته باشند .

برای ذخیره سازی زیر مسائل معمولا یه آرایه به اسم DP می گیریم که به تعداد ورودی های مستقل بُعد داره و هر بعد از اون یه اندازه بازه ای که اون ورودی می تونه تغییرات داشته باشه اندازه داره و تو هر سلول از این آرایه جواب متناظر با اون سلول قرار می گیره .

زمان مقدار دهی اولیه ، به هر سلول عددی رو نظیر می کنیم که هیچ وقت جواب تابع نباشه ( معمولا -1 )

مثلا تو تابع بالا ، فرض کردیم که مقادیر N! رو برای N < 100 نیاز داریم . پس ورودی تابع عددی بین 0 تا 99 خواهد بود و لذا اندازه DP رو 100 در نظر گرفتیم .

به عنوان مثالی پیچیده تر "ترکیب r تایی از n عضو" رو در نظر بگیریم .( n < 100 )

می دونیم این مقدار رو با ( C( n , r  نشون میدن . 

برای این مقدار رابطه بازگشتی زیر رو ارائه میدیم :

C( n , r ) = C( n-1 , r ) + C( n-1 , r-1 )

الان میبینیم که جواب مساله به دو متغیر مستقل ، وابسته شده پس برای ذخیره کردن زیرمساله ها به یه آرایه دوبعدی نیاز داریم . لذا برای محاسبه به صورت زیر عمل می کنیم .

int DP[100][100];

for( int i = 0 ; i < 100 ; i ++ )

{

    DP[i][0] = DP[i][i] = 1;

    for( int j = 1 ; j < i ; j ++ )

        DP[i][j] = DP[i-1][j] + DP[i-1][j-1];

}

همین طور میشه برای سوال های پیچیده تر این کار رو کرد .

انواع DP :

بسته به شرایط و نوع تابع بازگشتی ای که پیدا می کنیم برای سوال می تونیم از 2 تکنیک موجود استفاده کنیم .

1. روش بالا به پایین : تو این روش هر زمان که احتیاج به زیر مساله کوچکتری داشتیم ، مقدارش رو محاسبه می کنیم . این روش معمولا با تابع بازگشتی( از نظر مفهوم برنامه نویسی ) پیاده سازی میشه . برای مثال اول ( فاکتوریل ) از این تکنیک استفاده کردیم .

خوبی : این تکنیک از نظر فهمیدن و نوشتن کد ساده است .

بدی : 

کدش طولانی میشه .

چون از تابع بازگشتی استفاده می کنیم ، احتیاج به مقدار زیادی از stack داریم . برای تابع های بزرگ یا توابعی که عمق زیادی دارند نمیشه ازش استفاده کرد .( معمولا Stack Over Flow ) میشه .

اصطلاحا به تکنیکی که تو مثال اول استفاده کردیم ، Memoization یا به اختصار Memoize هم میگیم .

2. روش پایین به بالا : تو این روش شروع می کنیم از پایین با توجه به اندازه زیرمساله ها ، همه حالت هارو حساب می کنیم . می دونیم برای بدست آوردن مسائل کلی تر ، مساله رو به زیر مسائل کوچکتر تقسیم می کنیم . حالا چون بسته به اندازی کار کردیم ، حتما جواب زیر مساله ها رو داریم ( قبلا حساب کردیم ) و فقط کافیه از مقادیرشون استفاده کنیم .

تو مثال دوم ( ترکیب ) از این تکنیک استفاده کردیم .

خوبی : کدش کوتاهه و debug کردنش راحته .

بدی : مسائلی هستند که نیاز به تمام زیر مسائل کوچکتر ندارند ، فقط به بعضی از اونها نیاز دارند . تو این شرایط زمان اجرای کد طولانی میشه .

برای شروع چند یه سوال ساده از این مبحث کنید بد نیست .

سوال 11703 از سایت UVa

علاوه بر این مطلب خوندن مطالب این مقاله و حل سوالاتی که توش مطرح کرده توصیه میشه .

اگر موردی هست که به نظرتون جا افتاده یا ... بگید تا اضافه کنم .