सी में गतिशील प्रोग्रामिंग संसाधन?

Question

मैं कल एक नया फ्रेशर के रूप में ऑनलाइन Google परीक्षा लिखूंगा। जाहिर है, वे निश्चित रूप से गतिशील प्रोग्रामिंग पर एक समस्या पूछते हैं?

क्या कोई समाधान के साथ सी में डीपी समस्याओं के संग्रह के लिए एक अच्छा संसाधन जानता है? मुझे पता है कि डीपी & ने इसे किसी अवसर या दो बार इस्तेमाल किया है। हालांकि मैं परीक्षण में एक डीपी समस्या को दरकिनार करना चाहता हूं, सामान्य समस्याओं के पूर्व अभ्यास से संपर्क करना आसान हो जाएगा।

सी में समाधान के साथ किसी भी अच्छे संसाधन या समस्या सेट की अत्यधिक सराहना की जाएगी। धन्यवाद।

Answer 1

ठीक है, इसलिए मुझे उम्मीद है कि यह "लापरवाही सेल्फ-प्रोमोशन" के रूप में नहीं गिना जाएगा, क्योंकि ये सभी लिंक कोड स्निपेट्स हैं जिन्हें मैंने अपनी व्यक्तिगत साइट पर पोस्ट किया है। यदि यह अनुचित है, तो कृपया मुझे बताएं और मैं उन्हें नीचे ले जा सकता हूं।

1. न्यूनतम संपादित दूरी: को देखते हुए दो तार ए और बी, संपादन के कम से कम संख्या (सम्मिलन, हटाए जाने, या प्रतिस्थापन) के लिए आवश्यक लगता है

   यहाँ कुछ मज़ा डीपी समस्याओं कि काफी क्लासिक्स हैं ए को बी में परिवर्तित करें इसे लेवेनशेटिन दूरी कहा जाता है। (My solution)

2. इष्टतम अनुक्रम संरेखण: दो तारों ए और बी को देखते हुए, ए और बी को संरेखित करने के अनुक्रम में डालने वाले न्यूनतम अंतराल को ढूंढें इसे इसे सुलेमेन-वुन्श एल्गोरिदम कहा जाता है। (My solution)
3. सिंगल-स्रोत सबसे कम पथ: निर्देशित ग्राफ़ जी और एक नोड एस को देखते हुए, ग्राफ़ में एक दूसरे से नोड के सबसे छोटे पथों की लंबाई पाएं, मानते हैं कि किनारों को सकारात्मक या नकारात्मक हो सकता है लेकिन कोई चक्र मौजूद नहीं है । यह बेलमैन-फोर्ड एल्गोरिदम है। (My solution)
4. सभी जोड़े सबसे कम पथ: निर्देशित ग्राफ जी को देखते हुए, नोड्स के सभी जोड़े के बीच न्यूनतम दूरी खोजें। यह फ़्लॉइड-वॉर्शल एल्गोरिदम है। (My solution)

उम्मीद है कि यह कुछ हद तक उपयोगी है, और शुभकामनाएं कल!

Answer 2

Topcoder वेबसाइट अद्भुत है। सभी समस्याएं डीपी का उपयोग नहीं करती हैं, लेकिन कई लोग करते हैं। पिछली प्रतियोगिताओं से सभी समस्याओं के लिए नि: शुल्क पूर्ण पहुंच, जो 3 अलग-अलग कठिनाई के स्तर पर हैं, साथ ही समस्या लेखक से प्रत्येक समस्या के बाद के मिलान स्पष्टीकरण। इतना ही नहीं, लेकिन आप प्रतिस्पर्धा में किसी भी कोडर द्वारा सबमिट किए गए स्रोत कोड समाधान को तुरंत खोद सकते हैं।

थोड़ी देर के लिए वापस नहीं गया है, लेकिन वे कम से कम सी ++, जावा, सी # की अनुमति देते हैं और मुझे अब कई अन्य भाषाओं पर विश्वास है।

Answer 3

मैं आपको सुझाव देता हूं कि "बायोइनफॉरमैटिक्स एल्गोरिदम का परिचय" एक पुस्तक है। इसमें डीपी पर पूरी तरह से एक अध्याय है। जैसा कि @ टेम्पलेटैटिफेड ने न्यूनतम संपादन दूरी का उल्लेख किया है, इष्टतम अनुक्रम संरेखण में उनके साथ अन्य समस्या है। हालांकि कोई कार्यान्वयन नहीं है इसमें.तुम्हें इसे अपने आप करना है। लेकिन आपको उन्हें बहुत दिलचस्प लगेगा।

Answer 4

अभ्यास करने के लिए आप एसपीओजे में उपलब्ध समस्याओं में से एक ले सकते हैं। डीपी को आसानी से पहचानने के लिए आप Problems Classifier (कीवर्ड: डीपी) पर देख सकते हैं।