======سوال ۴======

امیرمحمد و سینا با هم یک بازی می‌کنند. امیرمحمد در جاده‌ای راه می‌رود و سینا او را دنبال می‌کند. آن‌ها
از قبل، شش اسکناس با ارزش‌های 
$\langle 8, 3, 6, 3, 10, 9 \rangle$
 را به ترتیب (از چپ به راست) در طول جاده انداخته‌اند. هر کسی زودتر به اسکناسی برسد می‌تواند آن را بردارد، ولی فرد عقب‌تر از او جلو می‌زند و ترتیب دو نفر عوض می‌شود. اگر فرد جلوتر اسکناس را برندارد، فرد عقب‌تر می‌تواند اسکناس را بردارد و ترتیب دو نفر هم عوض نمی‌شود. هر کسی می‌خواهد بیش‌ترین پول را برای خود جمع کند. حداکثر پولی که امیرمحمد می‌تواند در انتها جمع کند چە‌قدر است؟

  - ۲۲
  - ۲۱
  - ۲۴
  - ۲۳
  - ۲۵
<راهنمایی>
اگر فقط دو اسکناس روی زمین بود، امیرمحمد چه استراتژی‌ای در پیش می‌گرفت؟
</راهنمایی>

<راهنمایی>
اگر مقدار $f(n)$ را برابر با بیش‌ترین مقدار پولی که امیرمحمد می‌تواند جمع کند تعریف کنیم، در حالتی که فقط $n$ اسکناس آخر روی زمین باشند؛ مقادیر $f(n)$ را به صورت بازگشتی محاسبه کنید.\\
(به عنوان مثال، $f(2)$ جواب مسئله به ازای دنباله‌ی 
$\langle 10, 9 \rangle$
 است که برابر با ۱۰ می‌باشد.)
</راهنمایی>

<راهنمایی>
برای محاسبه‌ی $f(n)$، مقدار $g(n)$ را به طور مشابه برای حالتی که در ابتدا سینا جلوتر باشد تعریف کنید.
</راهنمایی>
  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]