طولانی‌ترین زیرتوالی مشترک
Longest Common SubsequenceLCS طولانی‌ترین زیرتوالی‌ای را پیدا می‌کند که در هر دو ورودی با همان ترتیب نسبی وجود دارد، ولی لازم نیست عناصر پشت‌سرهم باشند.
اول این مفهوم را در ذهن نگه دار
LCS طولانی‌ترین زیرتوالی‌ای را پیدا می‌کند که در هر دو ورودی با همان ترتیب نسبی وجود دارد، ولی لازم نیست عناصر پشت‌سرهم باشند.
چطور کار می‌کند؟ ساده و مرحله‌ای
معمولاً dp[i][j] طول LCS برای prefixهای دو رشته را نشان می‌دهد.
اگر کاراکترها برابر باشند مقدار diagonal + 1 می‌شود؛ وگرنه بهترین حالت حذف یکی از دو سمت انتخاب می‌شود.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
State را دقیق تعریف کن.
Transition یا choice را از stateهای کوچک‌تر بنویس.
Base Case را مشخص و بعد بین memoization، tabulation یا backtracking انتخاب کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای طولانی‌ترین زیرتوالی مشترک هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function lcs(a, b) {
const dp = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(0));
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
dp[i][j] = a[i - 1] === b[j - 1]
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[a.length][b.length];
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(mn)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی زیرمسئله‌ها overlap دارند و جواب از stateهای کوچک‌تر ساخته می‌شود DP مناسب است.
کجا معمولاً اشتباه می‌کنیم؟
- قبل از تعریف state سراغ recurrence نرو.
- DPای نساز که state space آن از خود مسئله بزرگ‌تر و غیرعملی باشد.
مدل یک پاسخ حرفه‌ای
حتماً Subsequence را از Substring جدا کن؛ این یکی از رایج‌ترین اشتباه‌های مصاحبه‌ای است.
طولانی‌ترین زیرتوالی مشترک چه مسئله‌ای را حل می‌کند؟
LCS طولانی‌ترین زیرتوالی‌ای را پیدا می‌کند که در هر دو ورودی با همان ترتیب نسبی وجود دارد، ولی لازم نیست عناصر پشت‌سرهم باشند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(mn) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
قبل از تعریف state سراغ recurrence نرو.