این کدشه. با زمان $O(n)$ عمل میکنه و حافظه $O(n)$ هم میخواد که در صورت سوال هر دو شو$O(n^2)$ خواسته بود. فقط توجه داشته باشید که تو ورودی اول n رو , بعد هم یه رشته از کاراکتر هارو وارد کنید(فاصله نندازین)مثلا:

5

10001

(کمی!!)توضیحات:

الگوریتم از این قراره:

رشته ورودی رو S میگیریم و $S[i]$ بیانگر حرف i ام رشته است.

سه تا تابع تعریف میکنیم:

$f0(n)$ : به معنی حداقل تعداد حرکات لازم برای تبدیل n حرف اول S از سمت چپ به 0.

$f1(n)$ : به معنی حداقل تعداد حرکات لازم برای تبدیل n-1 حرف اول S از سمت چپ به 0 و حرف n ام از سمت چپ به 1.

$g(n)$ : به معنای حداقل تعداد حرکات لازم برای تبدیل رشته $000...001$ به رشته $000...000$ طوری که طول رشته n است و رشته در سمت چپ S قرار دارد.برای مثال $ g(1)=1 $ و $ g(2)=3$.

هدف پیدا کردن $f0(n)$ است.

اول رابطه بازگشتی برای $g$ رو پیدا میکنیم.

اولا که چون میشه حرکاتو از آخر به اول انجام داد پس $g(n)$ رو میشه این طوری هم تعریف کرد:

حداقل تعداد حرکات لازم برای تبدیل رشته $000...000$ به رشته $000...001$ طوری که طول رشته n است و رشته در سمت چپ S قرار دارد.

فرض کنیم رشته $000...001$ رو داریم.چون تنها راه برای تبدیل 1 آخر رشته به 0 اینه که عدد قبلیش 1 باشه و همه عدد های قبل تریش 0 باشن(در واقع چپ ترین 1 باید قبل از اون باشه)پس اول باید رشته شامل n-1 عدد اول رو به $000...001$تبدیل کنیم که $g(n-1)$ حرکت میخواد.بعد عدد n ام رو 0 میکنیم که 1 حرکت میخواد و بعدش هم دوباره باید n-1 حرف اول رو تبدیل به 0 کنیم که $g(n-1)$ حرکت میخواد.یعنی:

$g(n)=2g(n-1)+1$

حالا رابط بازگشتی برای f0 و f1 رو پیدا میکنیم.

برای f0 داریم:

اگه عدد n ام S برابر 0 باشد آنگاه $f0(n)=f0(n-1)$ و اگر عدد n ام برابر 1 باشد آنگاه برای 0 کردن آن باید ابتدا n-1 عدد اول را به $000...001$ تبدیل کنیم که حداقل $f1(n-1)$ حرکت میخواهد و عدد n ام را عوض میکنیم که 1 حرکت میخواهد و سپس n-1 عدد اول را که $000...001$ اند تبدیل به $000...000$ میکنیم که $g(n-1)$ حرکت میخواهد.یعنی داریم:

برای f1 داریم:

اگر عدد n ام برابر 1 باشد آنگاه فقط باید n-1 عدد قبلی را 0 کرد که حداقل $f0(n-1)$ حرکت میخواهد و اگر عدد n ام برابر 0 باشد باید ابتدا n-1 عدد اول را به $000...001$ تبدیل کنیم که حداقل $f1(n-1)$ حرکت میخواهد و عدد n ام را عوض میکنیم که 1 حرکت میخواهد و سپس n-1 عدد اول را که $000...001$ اند تبدیل به $000...000$ میکنیم که $g(n-1)$ حرکت میخواهد.

برای کدش هم کافیه 3 تا آرایه بگیریم.مقدار دهی اولیه هم به این شکله:

$g(1)=1$

$f0(1)=s[1]$

$f1(1)=1-s[1]$

سوال جالبی بود. موفق باشید!