贪心：过了样例不等于对

唯一一类跑过样例仍然可能彻底错的算法。

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

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

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

贪心的正确性从来不是显然的：要么证明，要么被反例推翻，没有第三种状态。而贪心的反例往往需要三个以上元素、数值有意设计 —— 随手举的例子几乎必然通过，这就是它危险的地方。

这一份练两个工具：交换论证（假设有更好的解，把它第一处不同换成贪心的选择，证明不会变差）和构造反例。一说「我试了几个例子都对」就会被打断。

中间会拿两道长得几乎一样的题对照：活动选择贪心是对的，0/1 背包贪心是错的 —— 差在哪。

★★★★☆ · लगभग 35 मिनट · क्या परखा जाता है: 交换论证、构造反例、和 DP 的分界

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

शुद्धता की उपपत्ति स्टेट का डिज़ाइन

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

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

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

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

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

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

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

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

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

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

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

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

तीन फंदे

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

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