第 10 集 · A2 · 5 分钟
数学趣题 · 第10集 · Динамическое программирование
适合听读练习的俄语真实语料。片段原文开头：давайте обсудим динамическое программирование в приложении к задаче о траекториях кузнечика но перед этим обратимся к простой задаче из егэ на
中俄字幕
давайте обсудим динамическое программирование в приложении к
让我们讨论动态规划在
задаче о траекториях кузнечика но перед этим обратимся к простой задаче из егэ на
蚱蜢路径问题中的应用，但在此之前，我们先来看一道来自高考的简单题目，关于
количество траекторий
路径数量
на схеме городов со односторонними дорогами
城市网络图，其中道路为单向
представлен ориентированный граф, в котором нет циклов, он ациклический.
图中展示了一个有向无环图（DAG）
Надо сказать, что если бы был хотя бы один цикл, который можно было бы достичь в
需要说明的是，如果存在至少一个可在该路径中到达的环，
этой траектории, то можно было бы наматывать бесконечное количество траекторий
那么就可以生成无限多条不同的路径，
различных, задача теряла бы смысл.
问题将失去意义。
как считать количество траекторий из города А в город J
如何计算从城市A到城市J的路径数量？
Можно пытаться перебирать их.
可以尝试逐一列举所有路径。
Вот раз, два очевидные, да, какая- нибудь там три, да, четыре.
这里有一个、两个，很明显，对吧？还有个三，对吧？四。
Ведь есть еще пять, например, да?
毕竟还有五，比如，对吧？
Может я что- то не учел еще, ведь есть шесть, да, вот такая.
也许我还有什么没考虑到，毕竟还有六，对吧？就是这种。
А есть семь, прошу прощения, восемь.
还有七，抱歉，八。
Так, что- то я еще мог забыть.
嗯，我可能还漏掉了什么。
Ага, девять. Так, да?
啊哈，九。嗯，对吧？
Так, десять. одиннадцать.
嗯，十、十一。
Так, может быть вот такая двенадцать, кажется я ее не учел.
嗯，也许是这样的十二，好像我没考虑到它。
Вот такая тринадцать.
这样的十三。
Все ли я перебрал или нет?
我都列全了吗？还是没列全？
так можно себе запомнить что вот я так устно насчитал 13 некоторые школьники они так
这样可以记住：我心算得出13，有些学生会这样做
и делают а ведь этого делать категорически нельзя
这样做是绝对不允许的
надо здесь проблема тех же самых перечислений на самом деле.
这里的问题实际上与前面提到的枚举方法相同。
давайте попробуем вначале рассмотреть рекуррентно эту задачу представим себе что у
我们先尝试用递推法来分析这个问题：假设有一个起点城市A和一个终点城市Z，我们需要计算从A到Z的路径数量。
меня есть некий город а и есть некий финишный город z мне нужно посчитать количество
我有一个起点城市A和一个终点城市Z，需要计算从A到Z的路径数量。
траекторий из а в z в начале я должен определиться а из каких городов вообще есть
首先，我必须确定哪些城市有道路直接通往城市Z。
дороги в город z ну допустим два таких города есть.
假设这样的城市有两个。
X и Y. дорога из города x в город z у меня будет синей,
X和Y。从城市X到城市Z的道路我标为蓝色，
я её так назову.
我就这么称呼它。
Дорога из города y в город z
从城市Y到城市Z的道路。
будет красной.
会是红色的。
Я хочу заметить, что траектории, заканчивающиеся синей дорогой, синие траектории.
我想指出，以蓝色道路结束的轨迹是蓝色轨迹。
они именно этой дорогой заканчиваются.
它们正是以这条道路结束的。
Они у меня никак не могут совпадать с траекториями красными, которые заканчиваются
它们绝不可能与以红色道路结束的红色轨迹重合。
красной дорогой.
红色道路。
Дело в том, что у меня синие траектории вполне могли содержать y в качестве
这是因为我的蓝色轨迹完全可能包含y作为
промежуточного города.
中间城市。
Ну мало ли там у меня есть траектория, которая сквозь y, но потом через x и в z.
比如，我可能有一条经过y、再经过x、最后到达z的轨迹。
вполне возможно, или наоборот, из а, как сказать, траектории которые вот красные,
完全有可能，或者反过来，比如从a出发的红色轨迹，
они могут содержать x.
它们也可能包含x。
То есть, ну правда вряд ли и так и так, иначе цикл образуется между x и y.
也就是说，嗯，实际上无论是哪种情况都不太可能，否则x和y之间就会形成环。
Но в принципе я разделяю на синий и красный по последней финишной дороге.
但原则上，我根据最后一条终点路径将它们分为蓝色和红色。
Тут нельзя пройти и по синей, и по красной, потому что, ну как я вернусь от z, это
这里不能同时走蓝色路径和红色路径，因为，嗯，如果我从z返回，这……
уже опять же наличие цикла.
又会再次导致环的存在。
договорились. Я назову количество красных траекторий, пока мне неизвестное.
我们达成一致了。我将把红色路径的数量记作一个目前未知的量。
фразой а x, k ax, то есть количество траекторий из a в x.
用短语a_x,k_ax表示，即从a到x的路径数量。
Количество синих траекторий я назову k, ой, прошу прощения, синих k ax, а красных k
蓝色路径的数量我记作k，哦，抱歉，蓝色的是k_ax，红色的是k
ay. ну остается только что сказать извините ну давайте тогда назовем количество
_ay。嗯，剩下的就只有说声抱歉了，那么我们就把……
траекторий из а в z назовем его k из a в z,
从a到z的路径数量为k_az。
правда? ну и логично вполне, что все траектории, ведущие из a в z.
对吧？那么很自然地，所有从a到z的路径……
равно количеству траекторий из a в x плюс
等于从a到x的路径数量加上
количество траекторий из a в y.
从a到y的路径数量。
да ну можно себе даже нарисовать так представить тут какие то там траектории идут из
是的，你甚至可以画出来想象一下：这里有一些路径，从
а в х из а в у вполне возможно что там куча промежуточных точек еще раз даже вплоть
a到x，以及从a到y；其中很可能还存在大量中间点，甚至可能
до того что х и у да там пересекаются
x和y彼此相交。
Ясно? Эта идея рекуррентная.
明白了吗？这个思路是递归的。
Но я могу эту рекурсию чисто руками взять и начать от начала делать методом
但我可以用纯手工方式展开这个递归，并从起点开始，采用
динамического программирования.
动态规划的方法。
Мне нужно для каждого города записывать, сколько в него траекторий из города А.
我需要为每个城市记录从城市A出发到达该城市的路径数量。
Крайний случай— это сам город А.
边界情况就是城市A自身。
Сколько траекторий из города А в город А?
从城市A到城市A有多少条路径？
некоторые школьники думают ноль, когда я им рассказываю это.
当我讲到这一点时，一些学生认为是零。
Нет, ровно одна траектория из города А в город А стоять на месте.
不，从城市A到城市A恰好有一条路径：原地不动。
Это тоже траектория.
这同样是一条路径。
来源：Тимофей Хирьянов · CC BY 3.0