تالار گفتمان مانشت

گزینه ۴ صحیح است . نظر شما چیه ؟

منم4 رو زدم...

من ۳ زدم

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

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

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

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

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

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