المپدیا

روش به خاطرسپاری به نوعی یکی از حالت‌های حل مسئله به روش برنامه‌ریزی پویا است. پس اگر با این روش آشنا نیستید، پیشنهاد می‌کنم ابتدا متن آمده در پیوست را مطالعه کنید.
این روش (یعنی روش به خاطرسپاری) در واقع کارآمد بودن روش برنامه‌ریزی پویا را ارائه می‌دهد ولی در عین حال برای حل مسئله از ساختاری بالا به پایین استفاده می‌کند. ایده‌ی کلی این است که همان روش بازگشتی را به خاطرسپاری کنیم. یعنی اگر مقدار یک تابع بازگشتی را برای یک ورودی خاص محاسبه کردید، اگر یک دفعه‌ی دیگر همان تابع را با همان ورودی‌ها صدا کردید، جواب که تغییر نمی‌کند. پس اگر جواب قبلی را در جایی ذخیره کرده باشید، دیگر نیازی به محاسبه‌ی دوباره‌ی آن ندارید. (دقت کنید که در اینجا منظور از تابع، تعریف ریاضی آن است اما در برنامه‌نویسی، توابعی داریم که اثرات جانبی دارند یا از مقادیر تعریف شده به صورت عمومی (global) استفاده می‌کنند یا به هر دلیل دیگر جواب‌شان با ورودی یکسان، یکسان نیست و منظور ما این توابع نیستند.)
معمولا در استفاده از این روش، یک جدول از خروجی‌های تابع بر اساس ورودی‌هایشان در نظر می‌گیریم که در ابتدا مقدار ندارند و هر وقت که تابع را صدا می‌زنیم، ابتدا چک می‌کند که آیا جواب در جدول وجود دارد یا نه. اگر بود که آن را خروجی می‌دهد. اگر نبود، مقدار را محاسبه کرده و در جدول می‌نویسد و سپس آن را خروجی می‌دهد.

استفاده از این روش به جای روش عادی برنامه‌ریزی پویا چند برتری دارد. اولی این است که در روش عادی، بعد از حساب کردن تابع بازگشتی باید تازه به این فکر کنیم که خانه‌های جدول به چه ترتیبی باید پر شوند که قبل از محاسبه‌ی هر خانه، تمام مقادیر مورد نیازش محاسبه شده باشند. این کار در بعضی از مسائل برنامه‌ریزی پویا کار زیاد سختی نیست، اما در بعضی، امکان دارد کار ساده‌ای نباشد. ولی در روش به خاطرسپاری، اصلا نیازی به این کار نیست. فقط باید مطمئن باشیم که این کار ممکن است. یعنی در ترتیب محاسبات دوری وجود ندارد. در این صورت، ساختار بازگشتی کار پر کردن به ترتیب را به خودی خود انجام می‌دهد.
همچنین، در بعضی مسائل شاید نیازی به حل تمام زیرمسئله‌ها نباشد. یعنی مثلا شاید برای حساب کردن خانه‌ی $d_{0,n}$ نیازی به پر کردن مقادیر $d_{i,j}$ با فرض $i > \sqrt{j}$ نباشد. یا حتی شرط می‌تواند بسیار پیچیده‌تر باشد. در این حالت، اگر به روش عادی عمل کنیم، یا باید تمام شرط‌ها را پیدا کنیم و کاری کنیم که این مقادیر محاسبه نشوند یا این که امکان دارد پیچیدگی زمانی الگوریتم زیاد شود. اما اگر از روش به خاطرسپاری استفاده کنیم، خود به خود اصلا به این زیرمسئله‌ها احتیاج پیدا نمی‌کنیم و مقدارشان محاسبه نمی‌شود (در سوالاتی که واقعا پیداکردن ترتیب پر کردن خانه‌ها سخت است، باید این که واقعا در محاسبه‌ی تابع بازگشتی به دور می‌رسیم یا نه را چک کنیم چون در غیر اینصورت اجرای برنامه به پایان نمی‌رسد و روش حل نیاز به تغییر دارد و یا حتی می‌تواند اشتباه باشد.)
اما استفاده از این روش ضعف‌های خودش را نیز دارد. معمولا در مسائل برنامه‌ریزی پویا، ترتیب پر کردن بسیار ساده است و تقریبا تمام زیرمسئله‌ها باید محاسبه شوند تا جواب اصلی مسئله را پیدا کنیم. همچنین، بعد از پیدا کردن ترتیب پر کردن، معمولا کد روش عادی، بسیار ساده‌تر و کوتاه‌تر از مدل معادل آن با استفاده از روش به خاطرسپاری است. همچنین این روش به خاطر استفاده از ساختار بازگشتی، می‌تواند مشکلاتی با پر شدن پشته داشته باشد (البته تقریبا هیچ وقت اتفاق نمی‌افتد) و معمولا با یک ضریب ثابت از مدل عادی کندتر است که معمولا زیاد مهم نیست، اما در موارد خاص همین تفاوت کوچک می‌تواند حیاتی باشد.
این مشکلات باعث می‌شوند که در حالت عادی نیاز خاصی به استفاده از این روش نباشد.

برای مثال مسئله‌ی ضرب ماتریس‌ها را در نظر بگیرید. اگر با صورت مسئله و روش حل آشنا نیستید، می‌توانید تعریف آن را در پیوند بخوانید. کد زیر حل همان مسئله به روش به خاطرسپاری است:

Memoized_Matrix_Multiplication(a, n)
	for i from 1 to n
		for j from i to n
			d[i][j] = inf

	return solve_with_memoize(a, 1, n)

solve_with_memoize(a, i, j)
	if d[i][j] < inf
		return d[i][j]

	if i == j
		return d[i][j] = 0

	for k from i to j-1
		val = solve_with_memoize(a, i, k) + solve_with_memoize(a, k+1, j) + a[i] * a[k+1] * a[j+1]
		if val < d[i][j]
			d[i][j] = val

	return d[i][j]

همانطور که می‌بینید، دیگر نیازی نبود که به این فکر کنیم که خانه‌ها باید به چه ترتیبی پر شوند.
در متن کد یک نکته خودنمایی می‌کند، آن هم این است که باید برای نشان دادن این که مقدار خانه خالی است یا قبلا محاسبه شده، یا باید یک آرایه‌ی کمکی بگیریم که فقط همین موضوع را نشان دهد، یا همانند این کد، مقداری که هرگز نمی‌تواند جواب زیرمسئله باشد را قرار دهیم که اینجا از مقدار $inf$ یا بی‌نهایت ($\infty$) استفاده شده. در بسیاری از دیگر موارد از مقدار $-1$ نیز استفاده می‌شود.