جواب سوال ۳:
لم۱) یه جایگشت $n$ تایی داریم که بزرگترین زیردنباله ی صعودیش $m$ باشه و نزولیش $k$ باشه اگر و تنها اگر داشته باشیم:
$$m + k - 1 \le n \le km$$ خب برا لزومش: طرف چپ عبارت با این اثبات میشه که هر زیر دنباله ی نزولی و هر زیردنباله ی صعودی حداکثر تو یه عضو مشترکن، سمت راستشم با قضیه ی اردوش-ژکرس (البته دقیقن همون قضیه نیستا، ولی اثباتش عین اثبات اون قضیس!)

حالا از لزومه استفاده میکنیم و یه الگوریتم میدیم که جایگشته رو تولید کنه، بعد کفایتشم ثابت میشه!

این الگوریتم پویانه که اگه اون شرط بالا برقرار باشه حتمن جواب میده.

حالا اثبات بهینه بودنش!
لم۲)‌ به ازای هر جایگشت با اون شرایط گفته شده ($n, m, k$)، عضو اول اون جایگشته رو اگه بنامیم $x$، داریم $x \ge max(1, n-k(m-1) )$.
خب اینکه $x \ge 1$ که واضحه! میمونه ثابت کنیم $x \ge n-k(m-1)$. اگه $m=1$ بود خب ینی کل جایگشت باید نزولی باشه و طبق لم۱ دقیق در میاد که $k=n$، پس حله. اگه $m>1$ بود تو جایگشت مدنظرمون همه ی عدد هایی که بزرگتر از $x$ هستن رو درنظر میگیریم، یه جایگشت جدید داریم که $n-x$ تا عضو داره. حالا اگه بزرگترین زیردنباله ی صعودی جایگشت جدیده $m'$ باشه و نزولیش $k'$ باشه، داریم:
$$k' \le k$$ $$m' \le m - 1$$ $$n-x \le k'm'$$ در نتیجه داریم $n-x \le k(m-1)$ پس ینی $x \ge n-k(m-1)$ که همونیه که دنبالش بودیم! $^_^$

الان لم۲ ثابت میکنه اگه الگوریتم زیر به مشکل نخوره(ینی تا آخر پیش بره) حتمن بهترین جوابو میده:
عضو اولو میذاریم $max(1, n-k(m-1) )$. بقیه رو هم بازگشتی میایم حل میکنیم، با $n-1$ عضو، با این مشخصات: اگه $m=1$ بود میگیم نزولیش همون $m$ باشه و صعودیش $k-1$، وگرنه میگیم نزولیش $m-1$ باشه و صعودیش $k$. (اینا دقیقن حالت هایی هستن که اون نامساوی $x \ge max(1, n-k(m-1) )$ مساوی میشد.) حالا جایگشت بدست اومده توسط بازگشتیه رو برمیداریم و اون عدداییش که از عدد اولش بزرگتر-مساوی هستن رو ++ میکنیم و میشه جوابمون!
خب اینم با استقرا میشه اثبات کرد که حتمن شرایط لم۱ رو داره و اونا کافی هستن که جایگشت وجود داشته باشه؛ اینجوریم میشه گفت که جواب کد پویان رو اگه نگاه کنین میبینین باز شده ی همین روش بازگشتیه که توضیح دادم! پس این الگوریتمه حتمن تا آخر میره و عملن همون الگوریتم پویانه، پس الگوریتم پویان بهینست!

جواب 1 ج عدد رو به مبنای فیبوناچی ببرید (معلومه منظورم چیه دیگه) بعد هر سری هر 100 رو به 011 تبدیل کنید به صورت بازگشتی (میشه دی پی هم زد ولی ولش) اینم کد

توضیحه برنامه : اولش اون عدده رو میکنه مبنای فیبوناچی بعدش تابع رو صدا میزنه

توضیحه تابعه: تعداد حالت های تبدیل رشته s به رشته های دیگه از جایگاه k ام به بعد

اگه کسی توضیح اضافه خواست بگه بهش بگم :)

پانویس : مبنای فیبوناچی یعنی اینکه یه عدد رو به صورت جمع اعداد فیبوناچی بنویسیم به این صورت که هر سری بزرگترین فیبوناچی ممکن رو از این عدد کم کنی مثلا 30=18+8+3+1 خوب یعنی الان 18 یکه 13 صفره 8 یکه 5 صفره 3 یکه 2 صفره 1 یکه