لعبة نقطة وبرمجة ديناميكية

Question

أحاول حل متغير لعبة DOT مع البرمجة الديناميكية.

يتم لعب لعبة DOT العادية مع خط من النقاط. يأخذ كل لاعب إما واحدة أو نقطتين في نهاية كل منهما من الخط والشخص الذي تركه بدون نقاط ليحقق ذلك.

في هذا الإصدار من اللعبة ، لكل نقطة قيمة مختلفة. يأخذ كل لاعب منعطفات بديلة ويأخذ إما نقطة في أي من طرفي الخط. أريد أن أتوصل إلى طريقة لاستخدام البرمجة الديناميكية للعثور على مبلغ الحد الأقصى الذي يضمنه اللاعب الأول للفوز.

أواجه مشاكل في فهم رأسي حول هذا وأحاول كتابة تكرار للحل. نقدر اي مساعدة، شكرا!

Answer 1

الق نظرة على هذا الموقع: http://people.csail.mit.edu/bdean/6.046/dp/, ، وخاصة المشكلة رقم 10:

الاستراتيجية المثلى للعبة. النظر في صف من عملات N من القيم V (1) ... V (n) ، حيث n حتى. نلعب لعبة ضد خصم من خلال التناوب المنعطفات. في كل منعطف ، يختار اللاعب إما العملة الأولى أو الأخيرة من الصف ، ويزيلها من الصف بشكل دائم ، ويتلقى قيمة العملة. تحديد الحد الأقصى الممكن الممكن من المال الذي يمكننا الفوز به بالتأكيد إذا تحركنا أولاً.

هذا بالضبط ما تريد إذا كنت أقرأ منشورك بشكل صحيح. الحل بسيط للغاية ويتم شرحه جيدًا في رأيي.