Dynamic Programming

Dynamic Programming

بهترین راه یاد گیری حل مسئله است :-"

1- یک جدول n*m شامل 0 و 1 دارید ... بزرگ ترین زیر مستطیلی را که همهی خانه های آن 1 باشند را بیابید ...

پاسخ

2- یک رشته n-تایی به شما داده می شود (شامل integer) ... بزرگ ترین زیر رشته ی متوالی آن را بیابید ...

(Maximum Value Contiguous Subsequence)

پاسخ

3- یک رشته n-تایی به شما داده می شود ... بزرگ ترین زیر دنباله ی صعودی آن را بیابید ...

(Longest Increasing Subsequence)

پاسخ

4- شما n-جعبه دارید که جعبه i-ام  دارای ارتفاع hi عرض wi و طول di می باشد ...

هدف شما ایجاد یک پشته با ماکسیمم ارتفاع ممکن است ...

شما زمانی می توانید 2 جعبه را بر روی هم قرار دهید (ناقص)

(box stacking)

پاسخ

5- پس از آمدن سیل یک رودخانه ی بزرگ 2 ناحیه یک شهر را جدا کرده است ...

به صورت کاملا اتفاقی همه ی مرد ها در ناحیه ی جنوبی و همسران این مرد ها در ناحیه شمالی اند !!

مرد ها چون انسان های منظمی هستند به ترتیب با شماره ی 1 تا n به صورت یک ردیف کنار هم ایستاده اند ...

(از چپ به راست)

اما همسران این موجودات به نظم اعتقاد چندانی ندارند و به صورت درهم در کنار هم در یک صف ایستاده اند ...

هر یک از ایم مردان می خواهد به همسر خویش برسد ...

برای رساندن این 2 به یکدیگر کافیست یک خط از مرد به همسرش بکشیم ....

اما هیچ 2 خطی نباید با یکدیگر تلاقی داشته باشد زیرا تلاقی مرد ها را به یاد طلاق می اندازد !!

به شما نحوه ایستادن زن ها داده می شود ... شما باید بیشترین تعداد زوج را به هم برسانید ...

(Building Bridges)

پاسخ

6- به شما 2 string داده می شود شما 3 قابلیت دارید ...

تغییر یک حرف ... اضافه کردن یک حرف ... حذف یک حرف ...

هدف شما تبدیل string 1 به string 2 با کمتریین استفاده از قابلیت هایتان است ...

(Edit Distance)

پاسخ

7- شما دزدی بیش نیستید و به دزدی رفته این و یک کوله با گنجایش C با خود دارید ...

در محل وقوع جرم n شئ وجود دارد که شئ i-ام داری اندازه si و ارزش vi است ... (از هر شئ زیاد دارن !!)

هدف شما پر کردن کوله با بیشترن ارزش است ...

(Knapsack Problem)

پاسخ

8- همون قبلی ولی از هر شئ 1 دونه بیشتر ندارن ...

(0/1 Knapsack Problem)

پاسخ

9- شما n جسم با وزن هایی بین 0 تا k  دارید ...

هدف شما افراز این اجسام به 2 دسته است به نحوی که اختلاف وزن این 2 دسته مینیمم باشد ...

(Balanced Partition)

پاسخ

10- شما n نوع سکه دارید که ارزش سکه i-ام vi می باشد ... (v1 = 1)

هدف شما خرید جنسی با قیمت C با استفاده از کمترین تعداد سکه است ...

(Making Change)

پاسخ

11- شما n نوع سکه دارید که ارزش سکه i-ام vi می باشد ...

هدف شما یافتن تعداد حالت هایی است که می توان با این سکه ها جنسی با قیمت C را خرید ...

(Coin Change)

پاسخ

12- به شما 2 string داده می شود ...

هدف شما یافتن بزرگترین زیردنباله ی مشترک این 2 رشته است ...

(Longest Common Sub sequence)

پاسخ

13- به شما یک string داده شده است ...

هدف شما پیدا کردن بزرگترین زیر رشته ی Palindrome (از 2 طرف یکی !!) این string می باشد ...

پاسخ

14- یک لوله !‌ شامل n سکه داریم (n  زوج است و ارزش سکه i-ام  vi است) ...بازی 2 نفره ای در جریان است !!

در نوبت هر فرد او از یکی از 2 طرف لوله یک سکه بر می دارد سپس نوبت نفر دیگر است ...

بیشترین پولی که اگر آغاز کننده ی بازی باشیم بدست خواهیم آورد چه قدر است ؟

(Optimal Strategy for a Game)

پاسخ

15- به شما یک رشته شامل (or, true, false, xor, and) داده می شود ...

هدف شما پرانتز گذاری این عبارت به نحوی است که جواب آن برابر true باشد ...

(Counting Boolean Parenthesizations)

پاسخ

پست در حال تکمیل !! ...