منم۴ رو زدم...

من ۳ زدم

ایشالله که منظورش کاتالان بوده .. من ۴ زدم

من گزینه ۱ زدم.
چون فکر میکنم انتخاب ۲ از n جواب مسئله هست!
ولی ممکنه گزینه ۲ هم صحیح باشه و لازم باشه حالت اولیه هم براش در نظر گرفت.
در هر صورت گزینه ۴ خیلی بعیده درست باشه.

ویرایش:
الآن کلید دفترچه c رو دیدم زده گزینه ۲/
یعنی خاک تو سرم !! سوالی که خیلی مطمئن بودم درست زدم غلط شد!
الگوریتم رو که بلد بودم فاجعه جواب دادم امسال!

چه طوری گزینه ی ۲ بدست میاد؟

ضرب زنجیری بهینه n ماتریس چطوری بدست میاد؟
باید برای هر اندیس i و j ای، ضرب زنجیری بهینه ماتریسهای از i تا j رو بدست بیاریم.
خب حالا این چه تعداد زیرمجموعه رو به ما خواهد داد؟
باید ۲ عدد i و j از بین ۱ تا n انتخاب کنیم، البته با این شرط که i و j مساوی هم میتونن باشن. من خودم همین تساوی i و j رو در نظر نگرفتم و باعث شد جوابم غلط باشه! حالتی که i و j با هم برابر هستند در حقیقت حالت اولیه مساله خواهد بود یعنی ضرب زنجیری فقط ۱ ماتریس و در این شرایط واضح است که این عدد برابر با صفر خواهد بود.

پس جواب مساله خیلی راحت بدست میاد.
یک بار فرض کن i و j با هم برابر نیستند که این حالت برابر انتخاب ۲ از n خواهد شد.
یک بار هم فرض کن i و j با هم برابر هستند و این حالت هم برابر n خواهد شد.
از جمع ۲ حالت بالا گزینه ۲ بدست خواهد آمد.