در این مطلب، ویدئو تعداد طولانی ترین دنباله افزایشی – برنامه نویسی پویا – Leetcode 673 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:23:14
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:02,080
algomonster را با استفاده از لینک موجود
2
00:00:02,080 –> 00:00:05,040
در توضیحات بررسی کنید و از code neat برای
3
00:00:05,040 –> 00:00:08,080
10 دسترسی مادام العمر استفاده کنید سلام به همه خوش
4
00:00:08,080 –> 00:00:09,840
آمدید و بیایید امروز چند کد دقیق تر بنویسیم
5
00:00:09,840 –> 00:00:11,840
تا امروز مشکل
6
00:00:11,840 –> 00:00:14,160
تعداد طولانی ترین دنباله های
7
00:00:14,160 –> 00:00:16,640
افزایشی را حل کنیم و حتی قبل از اینکه وارد
8
00:00:16,640 –> 00:00:18,480
این مشکل شویم من فقط میخواهم اشاره کنم که
9
00:00:18,480 –> 00:00:20,560
این مشکل در واقع بسیار شبیه به
10
00:00:20,560 –> 00:00:22,160
مشکل دیگری است که قبلاً
11
00:00:22,160 –> 00:00:24,080
حل کردهایم که طولانیترین دنباله
12
00:00:24,080 –> 00:00:26,640
افزایشیافته است، همانطور که از نام نشان میدهد هر
13
00:00:26,640 –> 00:00:28,640
دو مشکل بسیار شبیه هستند، بنابراین این
14
00:00:28,640 –> 00:00:30,960
مشکل واقعاً ایده
15
00:00:30,960 –> 00:00:32,880
یافتن طولانیترین دنباله افزایشدهنده را گسترش میدهد.
16
00:00:32,880 –> 00:00:35,200
اساساً ما میخواهیم
17
00:00:35,200 –> 00:00:37,360
نه تنها طول طولانیترین
18
00:00:37,360 –> 00:00:39,120
دنباله افزایشیافته را پیدا کنیم، فرض کنیم
19
00:00:39,120 –> 00:00:41,200
طول آن چهار میشود، در این
20
00:00:41,200 –> 00:00:43,440
صورت میخواهیم پیدا کنیم که چند
21
00:00:43,440 –> 00:00:44,879
دنباله فرعی
22
00:00:44,879 –> 00:00:47,840
متفاوت وجود دارد که این
23
00:00:47,840 –> 00:00:49,760
طول را دارند که حداکثر طول درست است. بنابراین
24
00:00:49,760 –> 00:00:51,840
ما تعداد طولانی ترین دنباله های
25
00:00:51,840 –> 00:00:54,079
افزایش یافته را می شماریم و اساساً
26
00:00:54,079 –> 00:00:56,480
یک آرایه صحیح از اعداد به ما داده می شود
27
00:00:56,480 –> 00:00:58,000
میخواهیم برگردیم و تعداد
28
00:00:58,000 –> 00:01:00,640
طولانیترین دنبالههای افزایشیافته را بشماریم و لیستهایی
29
00:01:00,640 –> 00:01:01,760
که به
30
00:01:01,760 –> 00:01:04,319
اختصار آن را میخوانیم باید به ترتیب افزایشی باشد.
31
00:01:04,319 –> 00:01:06,560
32
00:01:06,560 –> 00:01:08,560
33
00:01:08,560 –> 00:01:10,320
میتوانید
34
00:01:10,320 –> 00:01:12,240
همه عناصر را بگیرید یا میتوانید زیرمجموعهای
35
00:01:12,240 –> 00:01:13,840
از عناصر را بگیرید، برای مثال ما
36
00:01:13,840 –> 00:01:15,840
5 را نمیگیریم یا فرض کنید ما
37
00:01:15,840 –> 00:01:19,119
4 را هم نمیگیریم، بنابراین با یک 1 3 7 باقی میمانیم
38
00:01:19,119 –> 00:01:21,200
و باید این مقادیر را به
39
00:01:21,200 –> 00:01:23,439
همان ترتیب نسبی که
40
00:01:23,439 –> 00:01:25,439
در آرایه ظاهر می شوند نگه دارید، بنابراین اساساً
41
00:01:25,439 –> 00:01:28,479
این یک زیر دنباله است، یک سه هفت
42
00:01:28,479 –> 00:01:30,640
یک دنباله بعدی، هرچند کافی نیست ما می
43
00:01:30,640 –> 00:01:32,479
خواهیم طولانی ترین موردی را که می خواهیم پیدا کنیم،
44
00:01:32,479 –> 00:01:34,960
پیدا کنیم، بنابراین در این مورد در واقع دو دنباله وجود دارد.
45
00:01:34,960 –> 00:01:39,040
lis’s uh one است یک سه پنج و
46
00:01:39,040 –> 00:01:41,200
هفت بنابراین ما چهار را حذف می کنیم زیرا اگر
47
00:01:41,200 –> 00:01:43,119
چهار را رها کنیم یک
48
00:01:43,119 –> 00:01:44,640
مرتبه افزایشی نیست درست نمی توانیم یک
49
00:01:44,640 –> 00:01:46,159
پنج داشته باشیم و سپس یک چهار داشته باشیم که
50
00:01:46,159 –> 00:01:48,079
بعد از آن می آید چهار کوچکتر است درست بنابراین ما
51
00:01:48,079 –> 00:01:50,880
نمی توانم فورهند را نگه دارم این o است اما
52
00:01:50,880 –> 00:01:53,280
53
00:01:53,280 –> 00:01:55,200
اگر پنج مورد را حذف کنیم، میتوانستیم این پنج مورد را حذف
54
00:01:55,200 –> 00:01:57,360
کنیم، همچنان به ترتیب افزایش مییابد،
55
00:01:57,360 –> 00:01:59,680
بنابراین میدانیم که طول آن
56
00:01:59,680 –> 00:02:02,240
چهار است، تعداد
57
00:02:02,240 –> 00:02:03,520
آنها چند نفر بود که دو نفر بودند. بنابراین ما
58
00:02:03,520 –> 00:02:05,360
دو را برگرداندیم بنابراین من به شما نشان می دهم
59
00:02:05,360 –> 00:02:06,799
که چگونه این مشکل را حل کنید و ما
60
00:02:06,799 –> 00:02:08,720
آن را با استفاده از برنامه نویسی پویا انجام می
61
00:02:08,720 –> 00:02:10,318
دهیم و آن را
62
00:02:10,318 –> 00:02:14,800
با n زمان مربع و مقدار o بزرگ از n حافظه اضافی حل
63
00:02:14,800 –> 00:02:17,280
می کنیم، اما قبل از ما حتی وارد
64
00:02:17,280 –> 00:02:19,040
راهحل dp میشویم، اجازه دهید با
65
00:02:19,040 –> 00:02:21,520
کمی شهود شروع کنیم، اگر میخواهیم
66
00:02:21,520 –> 00:02:23,760
هر زیر دنبالهای را با استفاده از
67
00:02:23,760 –> 00:02:26,800
این آرایه ورودی uh تولید کنیم، اساساً
68
00:02:26,800 –> 00:02:29,280
برای هر مقدار ورودی مانند یک یا سه
69
00:02:29,280 –> 00:02:31,519
یا پنج، واقعاً دو انتخاب داریم که
70
00:02:31,519 –> 00:02:33,599
میتوانیم یا انتخاب کنید که این مقدار را
71
00:02:33,599 –> 00:02:36,000
در دنباله اضافه کنید یا این مقدار را در دنباله اضافه نکنید
72
00:02:36,000 –> 00:02:38,000
، اگر
73
00:02:38,000 –> 00:02:40,319
درخت تصمیم را برای یکی انجام میدادیم، میتوانیم یکی را
74
00:02:40,319 –> 00:02:43,760
بگنجانیم یا میتوانیم از یکی
75
00:02:43,760 –> 00:02:45,280
بگذریم و میتوانیم این کار را با هر
76
00:02:45,280 –> 00:02:47,519
مقداری که به ما امکان تولید را میدهد انجام دهیم.
77
00:02:47,519 –> 00:02:49,040
هر یک زیر دنباله درست برای
78
00:02:49,040 –> 00:02:51,280
انتخاب دوم در اینجا داریم
79
00:02:51,280 –> 00:02:53,360
سه را شامل شود یا
80
00:02:53,360 –> 00:02:55,519
سه را در اینجا درج نکنیم همین انتخاب را داریم
81
00:02:55,519 –> 00:02:57,200
که سه را شامل شود یا سه را شامل نشود
82
00:02:57,200 –> 00:02:59,519
بنابراین فقط از دو مقدار اول
83
00:02:59,519 –> 00:03:01,519
می توانید همه دنباله های بعدی را ببینید که
84
00:03:01,519 –> 00:03:03,680
ما میتوانیم ایجاد کنیم، میتوانیم
85
00:03:03,680 –> 00:03:06,800
چهار تا از آنها را درست یکی سه یا فقط یکی
86
00:03:06,800 –> 00:03:08,400
درست بسازیم، جایی که عنصر دوم را رد
87
00:03:08,400 –> 00:03:10,480
میکنیم یا یکی را رد میکنیم و سپس
88
00:03:10,480 –> 00:03:12,800
فقط با سه مورد راست یا این باقی میمانیم که
89
00:03:12,800 –> 00:03:14,640
اساساً هیچ عنصری درست نیست.
90
00:03:14,640 –> 00:03:16,239
از نظر فنی یک لیست خالی یک
91
00:03:16,239 –> 00:03:18,000
دنباله است اما واقعاً
92
00:03:18,000 –> 00:03:20,239
برای این مشکل مرتبط نیست و اگر فقط به
93
00:03:20,239 –> 00:03:22,000
تولید درخت ادامه دهیم، میتوانیم تکتک دنبالهها را ایجاد
94
00:03:22,000 –> 00:03:23,920
کنیم، من
95
00:03:23,920 –> 00:03:25,680
از این منطق در این مشکل پیروی نمیکنم،
96
00:03:25,680 –> 00:03:27,680
زیرا ما همه
97
00:03:27,680 –> 00:03:30,720
دنبالهها را نمیخواهیم. ما فقط دنبالههای فرعی را میخواهیم،
98
00:03:30,720 –> 00:03:33,120
براین من از من
99
00:03:33,120 –> 00:03:35,519
ق برنامهنویسی پویا پیروی میکنم که به
100
00:03:35,519 –> 00:03:37,680
ا امکان میدهد طولانیترین دنباله افزایشی را تولید کنیم، بن
101
00:03:37,680 –> 00:03:40,080
براین اگر میخواهید لیست را به
102
00:03:40,080 –> 00:03:42,879
ورت بازگشتی پیدا کنید، می
103
00:03:42,879 –> 00:03:45,200
توانید یک دسته از انتخاب ها را انتخاب کنید اولین انتخاب
104
00:03:45,200 –> 00:03:46,799
این خواهد بود که اولین
105
00:03:46,799 –> 00:03:48,799
مقدار در ترتیب بعدی ما چه خواهد بود خوب ما می توانیم
106
00:03:48,799 –> 00:03:50,640
هر یک از مقادیری را که می توانیم انتخاب
107
00:03:50,640 –> 00:03:52,640
کنیم یکی را انتخاب کنیم که می توانیم سه را انتخاب کنیم و اکنون می توانیم
108
00:03:52,640 –> 00:03:55,760
برای هر یک از این شاخه ها پنج چهار یا هفت را انتخاب کنیم.
109
00:03:55,760 –> 00:03:58,159
ما فقط میتوانیم
110
00:03:58,159 –> 00:04:00,560
عناصر جدیدی را انتخاب کنیم که بعد از
111
00:04:00,560 –> 00:04:02,720
مقدار اصلی میآیند، بنابراین برای یکی ما مجاز
112
00:04:02,720 –> 00:04:04,480
به انتخاب یکی از چهار عنصری هستیم
113
00:04:04,480 –> 00:04:06,720
که بعد از آن برای سه عنصر قرار میگیرند، میتوانیم
114
00:04:06,720 –> 00:04:08,480
هر یک از سه عنصر دیگر را
115
00:04:08,480 –> 00:04:10,159
که بعد از آن قرار میگیرند و برای هفت
116
00:04:10,159 –> 00:04:11,840
واقعاً هیچ عنصری بعد از
117
00:04:11,840 –> 00:04:14,080
آن وجود ندارد، بنابراین ما نمی توانیم چیزی را انتخاب کنیم، بنابراین در
118
00:04:14,080 –> 00:04:15,680
این مورد، اگر
119
00:04:15,680 –> 00:04:17,279
با هفت شروع کنیم، این حالت پایانی است، طولانی ترین دنباله
120
00:04:17,279 –> 00:04:19,358
افزایشی که می توانیم ایجاد کنیم
121
00:04:19,358 –> 00:04:21,279
فقط هفت است، هیچ
122
00:04:21,279 –> 00:04:23,040
عنصر دیگری بعد از آن وجود ندارد. بنابراین این
123
00:04:23,040 –> 00:04:25,600
لیستی است که از هفت شروع می شود و برای
124
00:04:25,600 –> 00:04:27,680
چهار چاه چهار نیز بسیار ساده است
125
00:04:27,680 –> 00:04:28,960
زیرا فقط یک مقدار
126
00:04:28,960 –> 00:04:31,280
بعد از آن هفت می آید اما هفت
127
00:04:31,280 –> 00:04:32,880
در واقع بزرگتر از چهار است زیرا اگر
128
00:04:32,880 –> 00:04:35,040
یک لیست ایجاد کنیم، v نشانه ها
129
00:04:35,040 –> 00:04:37,919
باید به ترتیب افزایشی باشد برای چهار هفت
130
00:04:37,919 –> 00:04:39,600
بزرگتر از آن، بنابراین خوب است
131
00:04:39,600 –> 00:04:42,000
در مورد پنج خوب عنصر بعدی
132
00:04:42,000 –> 00:04:44,160
که بعد از پنج می آید یا می تواند
133
00:04:44,160 –> 00:04:46,560
چهار باشد یا می تواند هفت باشد، ما می دانیم که
134
00:04:46,560 –> 00:04:48,720
چهار حتی برای ما کار نمی کند زیرا
135
00:04:48,720 –> 00:04:50,479
کوچکتر از پنج است، بنابراین ما حتی
136
00:04:50,479 –> 00:04:52,639
این مسیر را درست در نظر نخواهیم گرفت، بنابراین
137
00:04:52,639 –> 00:04:56,160
لیستی که از پنج شروع می شود، اتفاق می افتد که پنج
138
00:04:56,160 –> 00:04:58,639
هفت از طول دو است و حالا بیایید
139
00:04:58,639 –> 00:05:00,479
به سه برویم، در واقع سه
140
00:05:00,479 –> 00:05:02,320
مقدار داریم که بعد از سه می آیند، می توانیم
141
00:05:02,320 –> 00:05:05,440
پنج را انتخاب کنیم. یا میتوانیم چهار یا میتوانیم
142
00:05:05,440 –> 00:05:07,520
هفت را انتخاب کنیم، هر سه این
143
00:05:07,520 –> 00:05:09,280
گزینهها معتبر هستند، زیرا هر سه
144
00:05:09,280 –> 00:05:11,440
این اعداد بزرگتر از سه هستند،
145
00:05:11,440 –> 00:05:13,680
اما اکنون ما چند مشکل فرعی داریم درست
146
00:05:13,680 –> 00:05:15,440
برای پنج، در واقع چند
147
00:05:15,440 –> 00:05:17,280
عنصر داریم که بعد از آن چهار میآیند و
148
00:05:17,280 –> 00:05:19,520
هفت و برای چهار دقیقاً یک
149
00:05:19,520 –> 00:05:21,360
عنصر داریم که بعد از هفت می آید و
150
00:05:21,360 –> 00:05:22,800
برای هفت می دانیم که هیچ
151
00:05:22,800 –> 00:05:24,800
عنصری بعد از آن وجود ندارد اما
152
00:05:24,800 –> 00:05:27,520
ممکن است متوجه شده باشید که این
153
00:05:27,520 –> 00:05:29,360
مشکل فرعی در اینجا و این مشکل فرعی
154
00:05:29,360 –> 00:05:31,680
نیز وجود دارد. ما در ابتدا
155
00:05:31,680 –> 00:05:35,039
میپرسیدیم که لیست از ساعت سه شروع میشود، اما اکنون
156
00:05:35,039 –> 00:05:37,360
میپرسیم لیست از ساعت پنج شروع میشود،
157
00:05:37,360 –> 00:05:39,919
اما به یاد داشته باشید که در واقع قبلاً
158
00:05:39,919 –> 00:05:42,639
آن مشکل را در اینجا حل کردهایم،
159
00:05:42,639 –> 00:05:44,400
خوب است که من تمام راه را از
160
00:05:44,400 –> 00:05:46,320
سمت راست شروع کردم و سپس شروع به
161
00:05:46,320 –> 00:05:48,400
کار کردیم. راه باقی مانده است زیرا اگر
162
00:05:48,400 –> 00:05:50,560
از اینجا شروع کرده بودم نمی دانستیم که
163
00:05:50,560 –> 00:05:53,680
قبلاً این مشکل فرعی را حل کرده ایم و تا به
164
00:05:53,680 –> 00:05:56,000
حال اگر با dp آشنا هستید ممکن
165
00:05:56,000 –> 00:05:59,440
است متوجه شده باشید که چرا این یک مشکل dp است
166
00:05:59,440 –> 00:06:01,199
زیرا می توانیم مشکل را به
167
00:06:01,199 –> 00:06:03,440
صورت بازگشتی حل کنیم. این و همچنین اجرای
168
00:06:03,440 –> 00:06:06,240
حافظه پنهان که ما را به یک o بزرگ
169
00:06:06,240 –> 00:06:08,000
از n راه حل مربع می رساند یا می توانیم
170
00:06:08,000 –> 00:06:11,759
مستقیماً به راه حل dp
171
00:06:11,759 –> 00:06:13,840
برویم زیرا اکنون متوجه شده ایم که با چه ترتیبی
172
00:06:13,840 –> 00:06:15,759
باید این مسائل را حل کنیم و
173
00:06:15,759 –> 00:06:18,240
باید مسائل فرعی را حل کنیم.
174
00:06:18,240 –> 00:06:19,759
به ترتیب معکوس باید
175
00:06:19,759 –> 00:06:22,880
طولانیترین لیست را پیدا کنیم که از هفت شروع میشود،
176
00:06:22,880 –> 00:06:24,880
سپس در چهار، سپس در پنج، سپس در سه
177
00:06:24,880 –> 00:06:26,880
و سپس در یک، و اگر این کار را به این صورت انجام دهیم
178
00:06:26,880 –> 00:06:28,880
، مجبور نخواهیم بود که به طور مکرر دقیقا همان زیر را حل کنیم.
179
00:06:28,880 –> 00:06:31,919
مشکلات، بنابراین در این مورد برای
180
00:06:31,919 –> 00:06:35,680
پنج، ما از قبل می دانیم که یک لیست از
181
00:06:35,680 –> 00:06:38,160
طول دو وجود دارد که از پنج شروع می شود
182
00:06:38,160 –> 00:06:40,639
و دقیقاً یک لیست از طول دو وجود دارد
183
00:06:40,639 –> 00:06:42,960
که از پنج شروع می شود، زیرا در این مورد
184
00:06:42,960 –> 00:06:44,560
برای زمینه این مشکل،
185
00:06:44,560 –> 00:06:46,800
ما فقط به دنبال لیست ها نیستیم. ما میخواهیم
186
00:06:46,800 –> 00:06:48,880
بدانیم چند نفر وجود دارند، زیرا این همان
187
00:06:48,880 –> 00:06:50,560
چیزی است که میخواهیم تعداد
188
00:06:50,560 –> 00:06:53,039
آن فهرستها را برگردانیم، بنابراین فقط
189
00:06:53,039 –> 00:06:55,039
کمی تصویر اضافه میکنیم تا درک این موضوع
190
00:06:55,039 –> 00:06:57,599
کمی سادهتر شود، اما
191
00:06:57,599 –> 00:06:59,680
با فرض اینکه واقعاً
192
00:06:59,680 –> 00:07:01,199
این مشکلات فرعی را حل نکنیم زیرا ما قبلاً
193
00:07:01,199 –> 00:07:02,479
آنها را حل کرده
194
00:07:02,479 –> 00:07:04,720
ایم و اکنون کشف کرده ایم که برای
195
00:07:04,720 –> 00:07:08,319
سه مورد، طول لیست سه است و می دانیم
196
00:07:08,319 –> 00:07:10,720
که در واقع دو عدد از آنها درست است،
197
00:07:10,720 –> 00:07:12,880
بنابراین ما دو جفت
198
00:07:12,880 –> 00:07:16,000
مقدار را دنبال می کنیم و می خواهیم بدانیم طول لیست چقدر است
199
00:07:16,000 –> 00:07:18,639
و ما میخواهیم
200
00:07:18,639 –> 00:07:22,400
بدانیم تعداد آن لیسها چقدر است، مثلاً چند دنباله
201
00:07:22,400 –> 00:07:24,639
از طول سه وجود دارد،
202
00:07:24,639 –> 00:07:26,479
خوب دو تا از آنها وجود دارد، حالا
203
00:07:26,479 –> 00:07:28,080
بیایید بفهمیم چگونه میتوانیم
204
00:07:28,080 –> 00:07:30,000
راهحل برنامهنویسی پویا را حل کنیم.
205
00:07:30,000 –> 00:07:32,160
حتی با استفاده از یک درخت تصمیم مانند
206
00:07:32,160 –> 00:07:34,639
این، منطق بسیار مشابه است، بنابراین همانطور که ما
207
00:07:34,639 –> 00:07:36,400
در حال حل مسئله بازگشتی بودیم،
208
00:07:36,400 –> 00:07:38,319
متوجه شدیم که حل مسائل فرعی،
209
00:07:38,319 –> 00:07:40,240
مسائل فرعی کوچکتر و سپس حل مسائل
210
00:07:40,240 –> 00:07:42,800
بزرگتر، دستور خوبی برای انجام این
211
00:07:42,800 –> 00:07:44,240
کار است، بنابراین ما به دنبال آن هستیم. برای شروع تمام راه
212
00:07:44,240 –> 00:07:46,720
از سمت راست و بنابراین این آرایه اعداد ما است
213
00:07:46,720 –> 00:07:48,479
، این مقادیر هستند، این
214
00:07:48,479 –> 00:07:50,879
شاخصها برای هر یک از اعداد برای هر یک از
215
00:07:50,879 –> 00:07:53,520
اینها هستند، فرض کنید از اینجا شروع میکنیم
216
00:07:53,520 –> 00:07:55,520
و مقداری که در dp ما خواهد رفت.
217
00:07:55,520 –> 00:07:58,240
آرایه یا کش یا هر چیز دیگری که می خواهید
218
00:07:58,240 –> 00:08:00,479
برای این کار استفاده کنید، به وضوح یک
219
00:08:00,479 –> 00:08:02,720
جفت مقدار داریم، بنابراین مقداری
220
00:08:02,720 –> 00:08:04,479
که در این نقطه قرار می گیرد
221
00:08:04,479 –> 00:08:08,080
نشان دهنده طول لیست است که از شاخص 4 شروع می شود
222
00:08:08,080 –> 00:08:10,960
. و مقداری که در اینجا می رود
223
00:08:10,960 –> 00:08:13,520
این است.
224
00:08:13,520 –> 00:08:15,840
تعداد این لیستها درست نشان میدهد که تعداد آنها به
225
00:08:15,840 –> 00:08:18,080
طور مشابه مقادیری است که به اینجا
226
00:08:18,080 –> 00:08:20,879
میروند شروع لیست را
227
00:08:20,879 –> 00:08:23,759
از شاخص 2 در آرایه ما نشان میدهند، بنابراین بیایید این کار را اکنون انجام دهیم
228
00:08:23,759 –> 00:08:25,599
تا از اینجا شروع کنیم، بدانیم
229
00:08:25,599 –> 00:08:27,520
که هیچ مقداری وجود ندارد. بعدش
230
00:08:27,520 –> 00:08:29,680
پس چی طول لیست
231
00:08:29,680 –> 00:08:32,958
صفر است نه زیرا برای هر لیستی مانند
232
00:08:32,958 –> 00:08:34,719
هر شاخصی که از آن شروع می کنیم
233
00:08:34,719 –> 00:08:37,200
حداقل یک مقدار درست در
234
00:08:37,200 –> 00:08:39,200
اینجا داریم، شاید هیچ
235
00:08:39,200 –> 00:08:42,320
مقداری بعد از آن وجود نداشته باشد اما خود هفت هنوز
236
00:08:42,320 –> 00:08:44,159
دنباله ای است. بنابراین میتوانیم بگوییم
237
00:08:44,159 –> 00:08:46,399
که طول آن یک عدد است که چند دنباله
238
00:08:46,399 –> 00:08:48,480
از طول یک دقیقاً یک وجود دارد،
239
00:08:48,480 –> 00:08:50,080
بنابراین واقعاً حالت پایه ما یک
240
00:08:50,080 –> 00:08:53,040
مورد بسیار ساده است، بنابراین در اینجا خوب
241
00:08:53,040 –> 00:08:54,880
در این مورد یک مقدار وجود دارد که
242
00:08:54,880 –> 00:08:57,120
بعد از آن دقیقاً یک وجود دارد. مقدار
243
00:08:57,120 –> 00:08:58,800
اکنون تنها چیزی که در اینجا واقعاً باید بررسی
244
00:08:58,800 –> 00:09:01,760
کنیم این است که مقدار بزرگتر از آن است که
245
00:09:01,760 –> 00:09:04,000
هفت بله بزرگتر از چهار است،
246
00:09:04,000 –> 00:09:06,320
بنابراین اگر این دو
247
00:09:06,320 –> 00:09:09,200
مقدار را با هم به عنوان یک دنباله اضافه کنیم این
248
00:09:09,200 –> 00:09:11,600
یک ترتیب افزایشی است بنابراین می
249
00:09:11,600 –> 00:09:15,680
توانیم طول آن را بگوییم یک به علاوه لیستی است
250
00:09:15,680 –> 00:09:19,120
که از شاخص چهار شروع می شود که می دانیم
251
00:09:19,120 –> 00:09:21,360
طول یک است، بنابراین آنچه که در اینجا قرار می دهیم
252
00:09:21,360 –> 00:09:23,680
در واقع 2 است و مقداری که
253
00:09:23,680 –> 00:09:26,320
قرار است در اینجا قرار دهیم 1 خواهد بود
254
00:09:26,320 –> 00:09:27,920
و دلیل آن این است که ما با گرفتن
255
00:09:27,920 –> 00:09:30,640
مقداری که af آمده است آن را وارد کنید و آن را
256
00:09:30,640 –> 00:09:32,640
به این یکی اضافه کنید زیرا این مقادیر
257
00:09:32,640 –> 00:09:35,120
با هم آنهایی هستند که لیست را ایجاد می کنند،
258
00:09:35,120 –> 00:09:37,279
این ممکن است در حال حاضر
259
00:09:37,279 –> 00:09:39,279
برای تنها دو مقدار منطقی نباشد، اما با
260
00:09:39,279 –> 00:09:40,959
مرور بقیه آرایه شرط می بندم که این
261
00:09:40,959 –> 00:09:43,279
برای شما معنی پیدا می کند. بنابراین برای پنج
262
00:09:43,279 –> 00:09:45,120
ما در واقع دو مقدار داریم که
263
00:09:45,120 –> 00:09:49,279
بعد از آن می آیند، یک مقدار چهار است، چهار
264
00:09:49,279 –> 00:09:52,399
بزرگتر از 5 است، نه، بنابراین ما
265
00:09:52,399 –> 00:09:54,800
در واقع نمی توانیم این را در دنباله خود وارد کنیم،
266
00:09:54,800 –> 00:09:57,040
بنابراین
267
00:09:57,040 –> 00:09:59,040
دیگر به 4 نگاه نمی کنیم، اما مقدار دومی داریم که
268
00:09:59,040 –> 00:10:02,720
می آید. بعد از 5، یک عدد 7 داریم و 7
269
00:10:02,720 –> 00:10:04,320
بزرگتر از 5 است، بنابراین آنچه که
270
00:10:04,320 –> 00:10:06,320
در اینجا برای طول لیست
271
00:10:06,320 –> 00:10:09,920
قرار می دهیم، 1 از 5 به اضافه لیستی است که
272
00:10:09,920 –> 00:10:12,480
از شاخص 4 شروع می شود که
273
00:10:12,480 –> 00:10:15,200
قبلاً 1 محاسبه کرده ایم و چگونه بسیاری از
274
00:10:15,200 –> 00:10:16,959
آنها دقیقاً 1 بودند. بنابراین چیزی که
275
00:10:16,959 –> 00:10:19,600
اینجا قرار می دهیم این است که یک به علاوه
276
00:10:19,600 –> 00:10:22,399
یک است که دو و یک در اینجا است
277
00:10:22,399 –> 00:10:24,720
زیرا یک لیست از طول دو وجود دارد که
278
00:10:24,720 –> 00:10:27,200
اگر این زیر دنباله uh را اکنون در سه ایجاد کنیم، می توانیم ایجاد کنیم.
279
00:10:27,200 –> 00:10:29,519
ما به
280
00:10:29,519 –> 00:10:32,160
مقدار بعدی که پنج است و
281
00:10:32,160 –> 00:10:34,959
پنج بزرگتر از thr است نگاه می کنیم این خوب است،
282
00:10:34,959 –> 00:10:37,839
بنابراین طول این لیست
283
00:10:37,839 –> 00:10:40,000
پنج به خودی خود فقط یک مقدار نیست،
284
00:10:40,000 –> 00:10:42,320
زیرا می دانیم که با شروع از پنج،
285
00:10:42,320 –> 00:10:45,360
می توانیم یک لیست با طول دو ایجاد کنیم،
286
00:10:45,360 –> 00:10:48,240
بنابراین با شروع از این مقدار سه،
287
00:10:48,240 –> 00:10:51,120
می توانیم یک لیست از سه ایجاد کنیم، اما فقط
288
00:10:51,120 –> 00:10:53,279
به این دلیل ما یک لیست پیدا کردیم که میتوانیم
289
00:10:53,279 –> 00:10:55,200
ایجاد کنیم، لزوماً به این معنی نیست که
290
00:10:55,200 –> 00:10:57,200
حداکثر است، من فکر
291
00:10:57,200 –> 00:10:58,800
میکردم همیشه حداکثر خواهد بود، اما
292
00:10:58,800 –> 00:11:00,959
لزوماً اینطور نیست زیرا
293
00:11:00,959 –> 00:11:02,800
میتوانیم به جای اینکه به پنج نگاه کنیم، میتوانیم
294
00:11:02,800 –> 00:11:05,600
به هفت نیز نگاه کنیم و ببینیم که اوه
295
00:11:05,600 –> 00:11:08,079
هفت بزرگتر از سه است، بنابراین لیز
296
00:11:08,079 –> 00:11:10,079
اوه که میتوانیم با سه و
297
00:11:10,079 –> 00:11:13,519
هفت ایجاد کنیم به طول دو خواهد بود، اما 2 لیست
298
00:11:13,519 –> 00:11:16,240
درستی نیست، ما یکی
299
00:11:16,240 –> 00:11:18,160
به طول 3 را پیدا کردیم. بنابراین ما 2 را
300
00:11:18,160 –> 00:11:20,000
اینجا قرار نمیدهیم. ما 3 را در اینجا قرار می
301
00:11:20,000 –> 00:11:22,399
دهیم زیرا حداقل یک لیست به
302
00:11:22,399 –> 00:11:24,560
طول 3 پیدا کرده ایم که 5 خواهد بود
303
00:11:24,560 –> 00:11:26,160
و می دانیم که الیاسی که از 5 شروع می شود
304
00:11:26,160 –> 00:11:29,519
5 بوده است، بنابراین این همان لیستی است که ما
305
00:11:29,519 –> 00:11:31,360
از آن عبور نمی کنیم. همه چیز
306
00:11:31,360 –> 00:11:33,279
به این دلیل است که این dp برای
307
00:11:33,279 –> 00:11:34,800
آن چیزی است این آرایه کوچک در
308
00:11:34,800 –> 00:11:37,120
اینجا برای ذخیره آن کار تکراری است که
309
00:11:37,120 –> 00:11:39,040
مجبور نیستیم به انجام آن ادامه دهیم
310
00:11:39,040 –> 00:11:40,720
، یک مقدار دیگر بعد از سه می آید
311
00:11:40,720 –> 00:11:42,399
و آن چهار است
312
00:11:42,399 –> 00:11:45,1