动态规划：状态定义才是那道坎

「看得懂题解、自己想不出来」，卡的几乎都是这一步。

प्रॉम्प्ट कॉपी करें, फिर कोई एक मॉडल चुनें। वह जवाब थमाने के बजाय इंटरव्यू लेने वाले की तरह दृश्य दर दृश्य आपसे पूछेगा।

जिस फ़ोन में ऐप लगा है, वहाँ सिस्टम सीधे ऐप खोल देगा। WeChat के अंदर बाहरी ऐप नहीं खुलते — पहले ब्राउज़र में खोलें।

कॉपी किए हुए पाठ के आख़िर में वही उत्तर-कुंजी है जिससे मॉडल आपको आँकता है। पहले खुद न पढ़ें — खुद तक पहुँचना ही असली बात है।

大家练的是转移方程，但转移是状态的推论：状态定对了转移基本自动，状态定错了怎么凑都凑不出来。所以这一份从头到尾只问状态，一个转移方程都不给你。

有一问是照妖镜：你说「dp[i] 表示前 i 个的最优解」，那么 —— 它必须包含第 i 个吗？两种读法对应完全不同的转移和答案位置，而一多半人从没分清过。

第三幕用环形数组把你的状态打穿，然后逼你说出什么叫「合法的状态」。

★★★★☆ · लगभग 45 मिनट · क्या परखा जाता है: 无后效性、状态维度、为什么转移是状态的推论

यह किसका अभ्यास कराती है

स्टेट का डिज़ाइन जटिलता

यह पाठ रिपॉज़िटरी में (उस फ़ाइल के अंत में कुंजी है — खोलते ही दिख जाएगी)

यह वाला कर चुके हैं?

साइन इन करके दर्ज करें कि यह अभ्यास कर लिया — अगली बार दिखेगा कि किस दिन किया था।

जिन्होंने यह किया, उनके नोट

अभी किसी ने नहीं लिखा। करने के बाद बताइए कि बातचीत से क्या निकला — किस दृश्य पर अटके, कौन-सा नतीजा बाद में बदला।

नोट लिखने के लिए साइन इन।

इसे कैसे इस्तेमाल करें

यह श्रृंखला सिखाती है, जिरह नहीं करती: यह आपको राह दिखाती है, न कि तब तक दबाती है जब तक कहने को कुछ न बचे। अटकने पर पहले पूछती है कि आप किस परत पर अटके हैं (कभी सुना ही नहीं / जानता हूँ पर क्यों नहीं पता / क्यों पता है पर लिख नहीं पाता), फिर तय करती है कि क्या देना है। एक ही जगह दो बार राह दिखाने के बाद ही सीधा उत्तर देती है — और फिर आपसे अपने शब्दों में दोहरवाती है।

कैसे शुरू करें

एक चुनिए, खोलिए, प्रॉम्प्ट कॉपी कीजिए।
एकदम नई, ख़ाली बातचीत में चिपकाइए, कुछ मत कहिए, पहले सवाल का इंतज़ार कीजिए।
कोड से पहले हाथ से चलाकर देखिए — यह आपको टोकेगी। लंबाई 2 के ऐरे पर हर क़दम चलाना, टेम्पलेट दस बार लिखने से बेहतर है।

बीच में कभी भी कहे जा सकने वाले चार संकेत

跳过 तुरंत अगले दृश्य पर
换个说法 इस जगह को दूसरे कोण से फिर समझाना
直说吧 पूरा उत्तर बताना, फिर मुझसे दोहरवाना
复盘 सीधे समापन पर जाकर पुनरावलोकन कार्ड निकलवाना

तीन फंदे

अंत वाला उत्तर-पत्र पहले मत पढ़िए — उसका «आम तौर पर लोग क्या ग़लत समझते हैं» वाला हिस्सा ही हर सवाल का जवाब है।
कोड लिखने पर मत टूटिए। एल्गोरिदम में कोड लिखना ही वह काम है जो «असल में समझा नहीं» को सबसे अच्छे से ढक देता है।
जब वह तारीफ़ करने लगे, उसे «मेरी तारीफ़ मत करो» वाला नियम याद दिलाइए। राह दिखाना दुलारना नहीं है।

हल ही नहीं सूझता? पहले स्टेट की परिभाषा कीजिए। सीमाएँ बार-बार ग़लत होती हैं? बाइनरी सर्च और प्रीफ़िक्स सम। समस्या का आकार पहचान नहीं पाते? मोनोटोनिक स्टैक और स्लाइडिंग विंडो। जटिलता वाली पर्ची कई और पर्चियों की नींव है — जल्दी कीजिए।