سوال ۷۹ کنکور ارشد علوم کامپیوتر ۱۴۰۰
اهمیت
۰/۵
کدام‌یک از مسائل زیر دارای الگوریتم پویا (dynamic) (با زمان چندجمله‌ای) است؟
(الف) یافتن فاصله هر دو رأس در یک گراف وزن‌دار جهت‌دار
(ب) یافتن طولانی‌ترین زیردنباله مشترک دو رشته
پاسخ صحیح: گزینهٔ C — هر دو
پاسخ تشریحی
Both problems are classic textbook examples solved by dynamic programming in polynomial time, so the answer is Both.
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#dynamic-programming#longest-common-subsequence#all-pairs-shortest-path#floyd-warshall#polynomial-time#optimal-substructure