مجموعه توانی
Power Setمجموعه توانی یک الگوریتم از دسته مجموعه‌ها و برنامه‌نویسی پویا است. این مسئله معمولاً با زیرمسئله‌های کوچک‌تر و stateهای تکرارشونده یا با تولید کنترل‌شده ترکیب‌ها قابل حل است.
اول این مفهوم را در ذهن نگه دار
مجموعه توانی یک الگوریتم از دسته مجموعه‌ها و برنامه‌نویسی پویا است. این مسئله معمولاً با زیرمسئله‌های کوچک‌تر و stateهای تکرارشونده یا با تولید کنترل‌شده ترکیب‌ها قابل حل است.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم مجموعه توانی ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع Varies by implementation / input constraints است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
State را دقیق تعریف کن.
Transition یا choice را از stateهای کوچک‌تر بنویس.
Base Case را مشخص و بعد بین memoization، tabulation یا backtracking انتخاب کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مجموعه توانی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی زیرمسئله‌ها overlap دارند و جواب از stateهای کوچک‌تر ساخته می‌شود DP مناسب است.
کجا معمولاً اشتباه می‌کنیم؟
- قبل از تعریف state سراغ recurrence نرو.
- DPای نساز که state space آن از خود مسئله بزرگ‌تر و غیرعملی باشد.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای مجموعه توانی در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی Varies by implementation / input constraints و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
مجموعه توانی چه مسئله‌ای را حل می‌کند؟
مجموعه توانی یک الگوریتم از دسته مجموعه‌ها و برنامه‌نویسی پویا است. این مسئله معمولاً با زیرمسئله‌های کوچک‌تر و stateهای تکرارشونده یا با تولید کنترل‌شده ترکیب‌ها قابل حل است.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
قبل از تعریف state سراغ recurrence نرو.