dynamic-programming-subtitle/subtitle.srt at main · ZKarbasi/dynamic-programming-subtitle · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

116
00:06:32,098 --> 00:06:36,098
و اینجا جاییه که کارایی بالا به دست میاد

117
00:06:36,185 --> 00:06:38,685
ما فقط به یکمی حافظه نیاز داریم تا این نتیجه ها رو در ذخیره کنیم

118
00:06:38,752 --> 00:06:40,151
تا بتونیم ازشون دوباره استفاده کنیم

119
00:06:40,187 --> 00:06:41,687
ما میتونیم از یه میز بزرگ استفاده کنیم

120
00:06:41,708 --> 00:06:43,908
که اغلب اوقات بهش میگن lookup table

121
00:06:43,961 --> 00:06:46,461
جایی که ما نتیجه هر محاسبه رو ذخیره میکنیم

122
00:06:46,461 --> 00:06:50,262
این میز برای هر عدد تاس، یک ردیف داره

123
00:06:50,288 --> 00:06:52,487
از ۱ تا هدف ما که ۱۰ هست

124
00:06:52,521 --> 00:06:55,521
و یک ستون برای هر جمع محتمل

125
00:06:55,521 --> 00:06:58,822
از ۱ تا هدف ما که ۲۸ هست

126
00:06:58,944 --> 00:07:02,444
ما میتونیم با پر کردن ردیف اول این میز شروع کنیم

127
00:07:02,576 --> 00:07:07,778
که همه جمع های احتمالی یک بار تاس انداختن رو نشون میده

128
00:07:07,944 --> 00:07:12,345
میدونیم که برای جمع ۱ تا ۶ دقیقا ۱ راه برای انجامش وجود داره

129
00:07:12,346 --> 00:07:16,545
و برای بقیه مقادیر 0 راه برای انجامش هست

130
00:07:16,747 --> 00:07:18,747
حالا ردیف بعدی رو پر میکنیم

131
00:07:19,047 --> 00:07:22,047
که نشون دهنده تمام جمع های احتمالی با دو تاس هست

132
00:07:22,079 --> 00:07:27,579
برای محاسبه هر از کدوم اینا فقط نیاز داریم که ۶ مقدار از  ردیف قبلی اضافه کنیم

133
00:07:27,879 --> 00:07:31,079
و برای ردیف سوم، تمام جمع های احتمالی با سه تاس

134
00:07:31,146 --> 00:07:35,047
هر مقدار از جمع ۶ مقدار از ردیف دوم به دست میاد

135
00:07:35,247 --> 00:07:38,447
به عنوان مثال تعداد حالاتی که از سه تاس استفاده کنیم

136
00:07:38,512 --> 00:07:40,512
و مقدار ۱۰ به دست بیاریم

137
00:07:40,579 --> 00:07:43,579
مساوی این هست که از ۲ تاس استفاده کنیم

138
00:07:43,812 --> 00:07:48,312
و مقادیر ۹ و ۸ و ۷ و ۶ و ۵ و ۴ به دست بیاریم

139
00:07:48,379 --> 00:07:51,379
به همین روش برای دست آوردن ۴ توسط ۳ تاس

140
00:07:51,379 --> 00:07:58,879
نیاز داریم جمع های ۳ و ۲و ۱ و ۰ و ۱- یا ۲- رو با ۲ تاس بدست بیاریم

141
00:07:59,081 --> 00:08:03,581
البته به دست آوردن هر جمعی که 0 یا منفی هست غیرممکنه

142
00:08:03,781 --> 00:08:09,281
پس قاعدتا میتونیم اون احتمالات رو دور بریزیم و فقط به بقیه توجه کنیم

143
00:08:09,490 --> 00:08:13,990
اگه ما به انجام این فرآیند ادامه بدیم و هر ردیف رو به ترتیب پر کنیم

144
00:08:14,103 --> 00:08:16,204
در نهایت آخرین ردیف رو پر میکنیم

145
00:08:16,370 --> 00:08:22,370
و میفهمیم چند حالت برای به دست آوردن جمع ۲۸ با ۱۰ تاس وجود داره

146
00:08:22,538 --> 00:08:28,538
و ما این کار رو با انجام یه محاسبه برای هر سلول روی این میز انجام دادیم

147
00:08:28,802 --> 00:08:30,004
ممکنه به نظر خیلی زیاد بیاد

148
00:08:30,071 --> 00:08:35,071
اما این خیلی خیلی کمتر از ۶۰ میلیون حالت تاس هست

149
00:08:35,138 --> 00:08:37,138
که ممکن بود در اون صورت بهش بر بخوریم

150
00:08:37,625 --> 00:08:41,225
این اصل پشت پرده چیزی هست که به اون dynamic programming میگیم

151
00:08:41,293 --> 00:08:43,793
با فرمول بندی یک مسئله به صورت بازگشتی

152
00:08:43,860 --> 00:08:48,860
یا به عبارتی تعریف یک مسئله بر اساس مسئله های کوچیک تر از همون مسئله

153
00:08:49,080 --> 00:08:51,278
و سپس استفاده از یک lookup table

154
00:08:51,278 --> 00:08:54,181
با ذخیره نتیجه محاسباتی که ما تا حالا انجام دادیم

155
00:08:54,182 --> 00:08:57,182
میتونیم اکثر مواقع به طور چشمگیری سرعت این الگوریتم ها رو افزایش بدیم

156
00:08:57,692 --> 00:09:00,692
و این نمونه از تکنیک ها به طور گستره قالب اجرا هستند

157
00:09:01,061 --> 00:09:03,061
این فقط در مورد تاس انداختن نیست

158
00:09:03,062 --> 00:09:06,562
این در مورد اینکه بفهمیم ما میتونیم همزمان مسائل جدید حل کنیم

159
00:09:06,562 --> 00:09:08,961
و جواب قبلی ها رو یا به یاد داشته باشیم

160
00:09:08,995 --> 00:09:12,495
و بفهمیم که با یادآوری کاری که تا الان انجام دادیم

161
00:09:12,629 --> 00:09:15,629
خودمون رو قادر میکنیم که ساده تر و با کارایی بالاتر

162
00:09:15,629 --> 00:09:19,629
مسائل بزرگتر و چالش برانگیز تر رو حل کنیم