同学们，这一讲我们来学动态规划。 那我们先从一个最简单的动态规划的例题数字三角形开始说啊。 这题目是这样的。就是有一个由数字组成的三角形，就是 第i行呢它就有i个数字， 那现在呢要做的事情就是从顶上 找一条路径，经过一些数字，到达这个底上， 到达底边，使得这条路径上面所经过的数字之和 最大，这条路7加8加4加6，就这条路径，它有一个和， 那我们走，从顶上往下走的时候呢， 每一步你只能往左下或者右下角，比如说它可以往这边走，往这边走，你不能跳到这里去， 那整个问题就要求你输出这个最大和就可以了。并不要求你把这个 路径给它表示出来， 然后这个三角形的函数是范围是100，数字的范围 是0到99，那反正这个最大和它就不会超出int的表示范围， 那这个题目怎么做呢？我们看它的输入格式是 第一行这个数字是代表三角形，一共有几行，然后就是数字三角形， 在这里，三角形看上去像是一个直角三角形， 那我们当然就用一个二维数组就能把它存下来，对吧，那这个时候呢，路径就变成 你可以是往正下方和右下方走了。变成这种情况了。 那这个题怎么考虑呢？如果有了 递归的思想，其实我们不难得出这个题的做法。 就是首先我们要用二维数组从它那个三角形 然后呢，我们二维数组假设叫做D，那当然 D(r,j)，它就表示这个三角形里面第r行，第j行，第r行第j列的这个数字了， 我们的i,j都从1开始算，然后呢我们 用一个函数Max(r,j)表示， 从D(r,j)这个数字到底边的各条路径中 最优的哪条路径上面的数字之和，那这个数字之和就包括D(r,j)了啊， 那整个问题实际上就在求MaxSum(1,1)对吧， 因为最顶上的数字是第一行，第一列的。那这是一个典型的递归问题了。 因为从这个D(r,j)出发嘛，你下一步只能走D(r+1,j)，或者是D(r+1,j+1)， 那到底往哪边走合适呢，那当然了，如果你发现从 r+1,j往下走，那个 最大和比从r+1,j+1往下走那个最大和更大，那你当然就会选择 从r+1,j往下走了对吧，这是很明显的， 因此，我们可以容易的写出这个递推的这个 式子，就是这个r==N，也就说这个数字它位于最底边上了，那 从这个数字到最底边的那个最大和就当然就是这个数字本身对吧， 因为它根本就走不动，那如果这个数字并不是在最底边上呢， 那我们要求Max(r,j)，而不是说有两条路走，对吧，一个是正的往下，另外一个呢是往右下方， 那哪条路更好呢？当然就是说如果我们已经求出了这个 正下方那个数字到底边的最大和，又求出了右下方那个数字到底边的最大和，那我们比较一下这两个最大和， 谁更大我就往哪边走，对吧，所以说我们这个MaxSum(r,j)它就等于两者之中比较大的那个，这两者是什么啊，就是 从r+1,j往下走得到最大和，就是正下方走了，这块呢， 这是从r+1,j+1往下走得到的最大和， 一般就是右下方的那个数字走到底边得到的最大和，对吧，那我们看看这两个里面哪个最大，我就 选择哪一个，然后呢，从这个地方往下走，得到的最大和当然就要加上这个r,j这个数字自身， 所以我们就有了这样一个递推的式子。 好，那这个递推的式子写出来以后，递归程序当然也好办了，对吧，这个程序很简单，我们一个数组D， 存上数字，然后呢，在main里面我们把这个 通过两重循环把D数组给读进来，然后我们就求函数MaxSum(1,1)，然后给它输出就行了。 那这个MaxSum呢当然就是个递推函数，是吧，就说， MaxSum(r,j)表示什么啊，表示从第r行，第j列的那个数值， 走到底边所能得到的最大和，那当然我们看如果i==n，那就说明它已经是最后一行的那个数字了， 那最大和就是那个数字它自己，是吧，否则呢，我们就要算一下 它正下方的那个数字走到底边得到的最大和是什么， 就说x，然后呢i,j这个数字它的右下方这个数字，当然就是i+1,j+1啦， 这个数字走到最底边得到的最大和是什么， 是y，那我们就在x,y里面取一个大的，就可以往大的那个方向走， 然后这个大的值呢加上这个数字i,j自身，当然就得到了就是从 数字D(i,j)往下走，能够得到的 最大和，对吧，递归程序，就这么简单。但是呢，同学们还不用高兴的太早， 这个数字三角形有100行，同学们可以估计一下，如果按这个程序要算出 一个结果，大概需要花多长时间，100行的数字三角形， 就不用想了，可以告诉你，哪怕你这个程序是从宇宙诞生那一刻开始算， 它算到今天，它还算不出个结果来。也就是说，这个东西是严重超时的，那为什么会超时呢？ 我们就来分析一下，原因到底在哪。 我们看到这个数字三角形，边上这些红色的数字就表示 在这个位置的Max上被求了多少次，啊， 那最顶上这个数字7，它的MaxSum的值当然它只求一次就够了，对吧， 然后我们可以知道，哎，3，这个数字的MaxSum也只需要求一次就行了， 8也只需要求一次，然后从这两个的MaxSum就能够得到7的MaxSum，但我们再往下看， 中间这个1，它的MaxSum是被求了几次呢？ 我们知道，你要求3的MaxSum值就得求这个1的MaxSum值， 然后你要求8的MaxSum值呢你又要求这个1的MaxSum值，等于这个1的MaxSum值呢被求了两次， 而我们求这个1的MaxSum值的时候就是要从这个1往下走，一直走到底的对吧， 一直走到往下底的， 所以你求这个1的数字的MaxSum，它的时间并不是常数， 它是一个递归的过程，从1这个位置一直往下走到底边才能算出来。 那么我们求3的时候，求3的MaxSum 的时候我们就从1一直往下走，走到底边，走了一次， 然后求8的MaxSum的时候我们又从1往下走，又走了一次，这当然就很浪费，对吧， 那同样的情况还发生在7,上面，那我们从7往下走到底边一共走了几次呢？ 我们可以算一下啊，我们从要求8的MaxSum的时候我们就要求7的MaxSum，于是就从7走到底边，走了一次， 然后我们要求1的MaxSum的时候我们又要从7往下走， 又走一次，但是1的MaxSum值被求了两次，所以说等于我们7 走到底边这个事情 在求1的MaxSum的过程中发生了两次，因为求了两次1的MaxSum，对吧，也就说， 从7走到底边这个事情一共发生了三次， 那同理，从4走到底边一共也发生了3次，然后你再往下看，最终这个2这个值， 被拿出来，这个事情发生了几次呢，它发生了6次， 因为你要求7的MaxSum的时候你就要把2拿出来，求4的MaxSum的时候你要把2的值拿出来， 然后7的MaxSum被求了3次，4的MaxSum也被求了3此，所以2的值一共被拿出来6次， 好，那我们现在实际上这个数字三角形里面 这个红色的数字就表示这个位置的MaxSum一共被求了几次， 那我们把所有这些值加起来，看一下， 这个是1次，这块是两次，这个是4次，这个是8次，这个是16次， 你最后算，算出来的结果就是什么啊， 总数就会是2的n次方减1，总的次数全加起来会是2的n次方减1，那时间复杂度当然就是 2的n次方，那如果这个n是100，2的100次方是多大，那就是从地球大爆炸到现在你也算不出结果来。 好了那怎么办呢？递归看来是行不通了对吧？ 所以这个时候就用到动归了，解决问题的关键就在于 我们要避免重复计算，对吧，这些地方，比如说我们要算的这个1的MaxSum，我第一次 已经算出来了，那我第二次再，比如说我求这个3的MaxSum的时候我已经求出了这个1的MaxSum的值， 那么在这种情况下，我应该把这个1的MaxSum值给它存在一个什么地方，存起来，对吧， 存起来以后当你要算8的MaxSum的值的时候呢，你要再去求1的MaxSum值， 可是1的MaxSum值呢我已经存在一个什么地方了，那我就直接把它拿出来用就行了， 我就不需要再从1一直再走到底边了， 这样不就节省了时间，避免了重复计算吗，对不对？ 啊所以问题的关键就是我们要每算出一个数字的MaxSum值(r,j)，我们就要把它存起来， 那下次再用到这个值的时候呢我们就不要递归，而是直接把存下来的值 拿来用就可以了，这就能够避免重复计算。那这个时候总的时间复杂度是多少呢？ 时间复杂度就变成了O(n)平方，为什么啊？ 因为这个数字三角形里面数字的总数是n(n+1)再除以2，对吧， 上面，顶上一个，然后接下来两个三个，1+n， 这个跟等差数列求和，而我们每一个数字 它到底边的最大和我们都只需要算一次就行了。 那这样需要算的总的次数就是这么多。时间复杂度就是n平方了。 好，那我们下面就来看一下怎么样写程序把这个算出来的值呢， 都存起来，避免这个重复计算。 我们依然写的是递归的这个程序，但这个时候呢我们多开了一个数组MaxSum， 用来存放算出来的这个最大和，那比方说MaxSum(i,j)这个数组的元素当然就代表从 (i,j)这个数字到底边的这个最大和。 那一开始这些最大和都没有算出来，对吧，所以在main里面呢我就把MaxSum(i,j) 全部初始化成-1，这个位置的值如果是-1，就表示它还没有被计算过， 然后呢我调用这个MaxSum这个递归函数，求MaxSum(1,1)的值输出就是问题的答案， 那MaxSum这个递归函数该怎么写呢，我们看，MaxSum(i,j)，求(i,j)这个数字到底边的最大和， 那要求这个数字最大和，我就不忙着递归，首先看一下MaxSum(i,j) 这个数组元素，它就代表(i,j)到底边的最大和，我看这个数组元素的最大值是不是-1， 那如果不是-1就意味着哎这个最大和曾经被算出来过， 那既然被算出来过，我就直接return就返回就行了，对吧？我就不要再去做进一步的计算了， 只有当它不为-1，就表示这个值并没有被算出来过的时候我才需要接着往下 做计算。那接着就是一个递归的过程跟前面那个 很像了。首先看i是不是第n行，如果是的话那我们就 我们就直接把D(i,j)这个数字存到MaxSum(i,j)里面，也就说就算出了这个MaxSum(i,j)的值了， 然后我们会return到MaxSum(i,j)，对吧，那如果i不是n的话，那我们就递归调用 MaxSum(i,j)，MaxSum(i+1,j+1)， 然后，这个时候我就能够算出这个MaxSum(i,j)这个 元素的值了，对吧，它等于什么呢，x,y两个大的再加上D(i,j) 整个程序最后，函数最后返回MaxSum(i,j)，那这样我们就做到了， 一个数字(i,j)它所对应的MaxSum的值，就最大和我们只需要计算一次， 那下次碰到再需要这个最大和的时候呢 我们就直接把上次算到它结果并且存起来那个值返回就行了， 这样我们就避免了多次的递归的重复计算。 那这个递归程序可以这么写，但实际上呢，递归嘛 它是有一层层的函数调用。如果递归次数特别多的话，你这个站可能会爆掉， 另外呢，递归函数调用本身也会有一些时间上的开销，那么实际上我们 不用递归，也可以解决这个问题。而且实际上我们会看到能够解决的更快。 而且更节省空间，那我们先来看一下如果我们不写递归的话该怎么解决这个问题。 好，现在我们把整个数字三角形画在这里。 就从那个D数组里面存的就是这个东西，对吧？ 现在呢，这个是这个MaxSum这个数组， 那这个MaxSum这个数组它的最后一行第n行嘛 这时候是n=5的对吧，它的第n行的值我们是能够一下就给它写出来的，对吧， 它跟D数组的最后一行是一致的。 好啦，那么我们最终要求的是在这个位置的值， 因为在这个地方是1,1对吧，所以我们最终要求的是在这个位置的值， 那怎么求这个位置的值呢？我可以从底下这一层一层层的往上推，最后能够算出这个位置的值。 怎么一层层的往上推呢？我们看啊，呃 现在最底下一层数字到底边的最大和我必须都求出来了，都在这，接下来我们要求2的这个数字到底边的最大和， 是多少呢？那就是4,5这两个数字里面 更大的，找一个出来，然后再加上2，对吧？ 那这个位置我们就知道了，2这个数字到底边的最大和就在这个位置，那就是5+2就是7， 对吧，哎就是7，好，那么这个 接下来要求7这个数字到底边的最大和，那就是5和2这两个数字里面选一个大的， 再加上7它自己，于是我们就写出来是12， 同理，要求4到底边的最大和就是2和6，这两个数字 里面选一个大的，然后再加上4就是10，然后从5和6这个位置就是10， 接下来我们要求8到这个底边的最大和，那当然就是 这两个数字到底边的最大和选一个然后再加上8对吧？那这两个数字到底边的最大和在哪呢？在这，对吧？ 那我们当然是选12,12+8等于20，我们就写出来20，同理呢，就这两个里面我们选出来一个大的， 加上1，这里就是能够得到13，依次往上类推，最后我们能推出这个30， 中间过程就掠过去了， 那这个过程并没有什么递归的这个概念在里面，对吧？那我们可以写一个程序模拟这个过程， 这反正是一个二维数组嘛，最后一行的值已经知道了，我们一层层 往上推，把这个最左上角的那个数字的元素求到就完了嘛，对吧， 这个过程可以用递推来实现而不需要写递归函数，那具体的程序当然也是很简单的。 那么这种递推形式我们称之为人人为我的这个递推形式，为什么称为人人为我呢？ 我们后面再解释。那有人人为我嘛，自然肯定就会有我为人人，对吧，要不然多不像话啊， 那么这两种情况为什么给这个名字，等会再解释。 现在我们看到在这个程序就变得短了，对吧，在这里面呢我们首先 在这个程序里面在输入完D(i.j)以后呢，我们就把MaxSum最后一行给它求出来了， 最后一行的值正好就等于D的最后一行的值， 接下来我们就要从n-1行向上一直推到第一行， 啊，向上推到第一行，那对于每一行我们要 从左到右求出每一个数字的最大和，那第I行它自然有i个数字， 就是每一个数字的最大和MaxSum(i,j)它等于什么呢？它跟它下一行的 两个数字有最大和关系，这就是MaxSum(i+1,j)和MaxSum(i+1,j+1)， 我们在这两者里面取一个大的，再加上D(i,j)就是MaxSum(i,j)的值。 那这里面就有一个问题了，你需要求第i行的MaxSum(i,j)的时候， 那么第I+1行的那些数字的MaxSum是不是都已经肯定求出来了呢？ 答案是没有问题的，因为我们这个循环不是从下往上的，对吧？ 那我们要求上一行的MaxSum(i,j)的时候下一行的MaxSum(i,j)肯定都已经求完了。 我们这MaxSum(i,j)最早求出来的是最底下一行的，然后行从n-1，就是往上走， 第n行的求出来，第n-1当然也就能求出来，对吧，第n-1行求出来， 第n-2行也能求出来，所以这个程序是没有问题的， 那么这个程序的时间复杂度是多少呢？我们看到， 这个两重循环典型的时间复杂度是n平方， 但是我们看到这个动归程序很典型的就是要从已知推出未知， 那这个程序呢还不够好， 就是说我们还可以改进，在哪可以改进呢？就是我们在空间上面可以改进，这个MaxSum二维数组 有点浪费了，实际上我们只需要 不需要那么多的存储空间，为什么呢，因为我们知道， 我们在从这一行的MaxSum值算出上一行的MaxSum值以后， 这一行就没有用了，对吧， 那我们再要再算上一行的MaxSum的值，实际上我可以把算出来的值直接就存在 这个地方，对吧，不用再寻找空间，直接存在 原来下一行的位置。然后呢，这个新的值再算出来上一行的，就又存在这。 只要有两行就交替使用， 就足够了。这种形式呢叫做滚动数组，能够节省空间。那我们来看看为什么只要一行就够。 好，实际上我们在这里列出了这个MaxSum最底层的那一行， 它对于这个D数组里面这数字的MaxSum，那我们要求 2这个数字的MaxSum，那我们当然就从4,5这两个数字找一个大的，5然后再加上2， 可以算出一个7，对吧，那我们这个7要用到存放到别处吗？ 我们发现，哎，4这个最大和，它跟5一起推出7以后，这个数字就再也没有用了，那么 我们就可以直接把7放在这， 我们不需要为7找别的地方，那同理，我们有5和2两个最大和 算出了这个7这个数字的最大和 它是多少啊？它是12，那12我们也 用不着找别的地方存放，我们直接存放在5这个位置，就行了。 就这样。那接下来，由2,6两个最大和算出来4所对应的最大和是10我们也 不用找别的地方放，我直接放在这， 以此类推。然后呢， 然后接下来我们要求8这个数字的最大和了，它可以通过7,12这两个数字 算出来结果是20，我们放哪呢，7这个位置已经没有用了，对吧，所以直接放在7这个位置就行， 就是这样。然后也可以把13也放在这。 以此类推我们就知道我们最后问题的答案可以放在 什么位置啊，就是放在这个位置，就算出来是一个30放在这个位置，就行了。 这时候我们看来只需要一行就可以存放 运算过程中所有的这个最大和了，但实际上我们连这个额外的 一行都不要，为什么，我们直接用D的第n行，就是那个最底下一行替代MaxSum就可以了。 因为D的最底下那一行它存放的值本来就是MaxSum最底下那一行的值，对吧？ 然后D的，然后MaxSum的n-1行的值求出来了以后呢， 那个MaxSum的第n行，也就是D的第n行也就没有用了， 所以我们可以改进一下。 我们不再还是MaxSum数组，而是用一个MaxSum的这个指针。 那我们让这个指针呢指向D的第n行， 那接下来求所有的max sum过程都全部发生在D的第n行上面了。 所以我们看到其他部分跟前面的程序是一样的，只不过这个max sum 到底是在什么地方存放，变成了 用D的第n行来存放max sum。 那我们的这个程序比刚才的那个空间上又做了一定的这个优化，当然实际的复杂度是 没有什么改变的。那数字三角形这个程序我们就讨论过了。 那下面我们就要讲讲这个，呃，动规到底怎么考虑问题。 也许你比较熟悉递归的这个写法，那我们前面看到了，数字三角形可以写成递归的程序，它会超时， 超时的原因在于那些中间的结果已经算了好多遍，那我们改进一下，就把一个结果算出来，就存起来， 那下次再用到它的时候就不用重新算了，写出来的程序呢还是递归的，那那样一个递归的程序我们称之为 记忆化的递归，对吧，它是一种动规实现的一种形式， 叫做记忆化的递归或者叫记忆递归。 那动规程序大多数情况下，还写的就是不是递归而是有一个数组在那里从已知推未知这样一个过程。 那我们怎么把一个递归的程序转变成这个标准的动规，就是非递归的那种程序呢？ 就有一般的转化方法，你可以用递归的办法去想， 假设你现在要解决这个问题你想出来这个递归的函数它有n个参数， 那我们就可以定义一个n维的这个数组，啊，用来存放， 计算的这个结果，而且这个数组的，下标， 它的范围就是递归函数参数的取值范围，一个参数对应一维，这一维到底有多大， 就对应于这个参数它的取值范围。 那么这个时候这个数组元素的值就相当于这个递归函数的返回值， 比如数组元素下标是i键，就相当于你这个递规函数的参数是i键的时候这个返回值。 然后呢这个数组，你就必须要付给里面， 某些元素一个初值，这个初值你不需要通过什么递归，你就直接能够很简单地算出来， 这些初值我们就称之为边界值，边界值它不一定是位于数组的 边上的，它有可能在数组的中间什么地方，反正就一开始这个，很容易就 能算出来这些初始值吧，我们就称为这个边界值。 然后这个动规的过程就是从已知推出未知，也就是说从这个边界值开始，逐步 已知推出未知，然后填充数组，然后直到呢，你把想要的那个数组元素的值， 它代表了问题的答案，你把那个元素的值给推算出来，这个问题就结束了。 那这样一个推算的过程就跟递归函数的计算过程， 表面上看是有点正好是相反的啊，因为递归我们从上到下， 但在数字三角形里面递归是从上到下的，但是，递推的时候从下到上，表面上看 是有点相反的，当然递归，归根到底执行的时候它还得是要从下往上算的， 只不过我们写程序的逻辑看起来，一个是从上到下，一个是从下到上。 那我们要用动规来解决问题，有一般的这个思路的， 怎么想呢？首先我们要把这个原问题分解成这个子问题， 那分解子问题这种想法嘛， 它跟递归的想法是很像的，对吧，我们把原问题分解成若干个子问题， 这个子问题呢它跟原问题形式是相同，或者说很类似， 只不过是它的规模变小了，然后这个子问题要是都解决了那原问题就解决了。 你数字三角形这个这个题目为例，我们要算出， 呃，顶上那个数字到底边的最大和，这是一个原问题，那子问题是什么呢？ 子问题就是它正下方的那个数值到底边的最大和， 和它右下方这个数值到底边的最大和，这就是两个子问题。 这两个子问题如果解决了，那我们取那个最大和，那个大的那个方向走， 那原问题就能解决了。对吧。那么我们在数字三角形这个例子里面， 我们分解出来的子问题跟原问题是一模一样的， 但是子问题所对应的数字呢就往下走了一层，也就是说它的规模变小了。 当然在这个动规解决的时候，我们要注意子问题的解一旦求出，你肯定就要保存起来。 不可能说你下次用到的话，还要再重新算一遍，对吧。这样我们要确保每一个子问题它肯定都只能算一次， 算完了就存起来。那第一步要分解子问题，第二步呢， 要做动规你就要， 确定出一些所谓的状态的东西，然后呢，我们要在状态之间进行转移， 那到底什么叫状态呢？我们会把和子问题相关的 各个变量的一组取值称为一个状态， 那一个状态它就对应于一个， 也可能对应用于多个子问题，然后某一个状态下面就有一个值， 一个状态的值是什么呢？就是这个状态所对应的子问题的解。 那如果状态对应多个子问题的话，那这个状态的值就是多个子问题的解。 那到底怎么样确定状态啊， 就是所有的状态的集合构成问题的这个状态空间，那状态空间的大小 就是和这个与用动态规划解决问题的时间复杂度是直接相关的， 那我们在这个数字三角形的例子里面呢一共有n乘以n加一加二个数字， 然后这个问题的状态空间里面就一定有n乘以n加1除以2的状态。 那么，我们这个状态到底指的是什么呢？我们以数字三角形这个例子为例。 前面提到，什么叫状态呀？和子问题相关的各个变量的一组取值称为一个状态，那么在数字三角形里面， 和子问题相关的变量是什么？首先你说子问题是什么？子问题就是， 第i行列那个数值到底边的最大和，这就是子问题。 那么跟子问题相关的变量有几个，就两个，就是那个i件，就是 数值的行，和数值的列。i键这两个变量。 那么这个i键我们就它的一组取值，我们就称为一个状态， 它有多少种取值那就有多少个状态。 那么我们说一个状态对应一个或者多个子问题，那在数字三角形的例子里面，i键就是这个数字的位置就是一个状态， 那么这个状态的值是什么呢？就是，这个状态对应的子问题是什么呢？就是从这个， 状态所代表的那个数值到底边的那个最大和，就是它的子问题。 那这个状态的值就是个子问题的解，也就是说这个最大和。 那我们在数字三角形里面呢，我们知道整个问题的时间复杂度是状态数 乘以计算每个状态所需的这个时间，那在数字三角形里面，计算每个状态所需的时间是常数的，所以复杂度就是 跟状态的数目是一个级别的。因为我们每一个状态都只需要经过一次 就行了，所以我们做动规的时候首先要分析子问题，然后把子问题跟状态对应起来。 那我们经常能够碰到的情况就是K个整形变量能够构成一个状态，比如说数字三角形里面的 行号和列号这两个整型变量就能够构成一个状态，对吧，那么我们这个K个整型变量它的取值范围分别是n1到nk， 那我们就可以用一个K为数组，array，N1,N2,......NK来存储各个状态的这个值，啊。 就是每一个数组的维，每一维有多大，就是 这一维所对应的那个变量，它的取值范围。 那这个我们这个数组来存放， 一个数组元素就可以存放一个状态的值，那这个值它不一定就是一个整数或者是浮点数， 它可能也需要一个数据结构才能表示。比如说它可以是一个对象，是个iii之类的，它可以很复杂，那这个值 它能够表示一个子问题的解，那一个子问题的解未必就是用一个整数或者浮点数来表示，对吧。 那在给出了状态定义以后的我们接下来要做的事情就是，我们要 算出一些初始状态，也称为边界状态的这个值，这些值反正就是一眼能够看出来的， 那比方说以这个数字三角形这个题目为例那初始状态等于就是底边上的这些数字， 每一个底边上的数字对应一个初始状态，那这个初始状态的值就是这个数字的大小。 呃， 确定一些初始值状态的值以后啊，我们就要接下来做的事情就是从已知推未知，就是想办法从这个 状态已知的那些值，啊，算出来一些未知状态的这个值，这是通常的做法，倒不是说 百分之百都是这么做啊。总之，我们要找出，在不同的状态之间如何迁移？就是从， 如何从一个或者多个值已知的状态，求出另外一个状态的值。 啊， 这个就是人人为我，递推行的这个定义，因为 我要算当前的这个状态值得时候，我得事先知道其他好多个状态的值，然后呢， 从其他个好多状态的值，能够算出，我的值，我这个状态的值。那其他好多状态，就相当于是人人， 我就是，当前要求的这个状态的值。由好多个已知推出未知，所以这就是人人为我。 人人为我并不是唯一的动规的形式啊， 那状态的转移可以用这个递推公式来表示， 这时候递推公式也被称为这个状态转移方程，那比如说数字三角形的状态转移方程就是这样了。 那这个r键，第r行第j 列的这个的值，它等于 D r键，如果说 r就是第n行的话，否则就等于它下面两个数字的最大和，取一个最大的，再加上第r键。 这就是状态转移。那下面我们就要说了就是 那动规，我们说了它解决问题的基本思路，那动规它到底用来 解决什么类型的问题合适呢，就是，如果你发现一个问题它满足下面的两种特点之一， 它就适合用动规来解决。这两种特点就是第一就是，最优子结构的性质。 什么叫最优子结构性质啊？就是如果一个问题，它能分解成一个一些子问题， 而且这个问题的最优解，它所分解出来的那些子问题它们的解一定是最优的， 那这样的问题，我们就称之为具有最优子结构这个性质，像数字三角形，它就有最优子结构性质，对吧， 你从一个数值到底边的最大和，那么分解成，这个它两个，两个，底下的两个数字到底边的最大和。 那只有在底下的那两个数字到底边，走的路径是最优的情况下， 你再往上面走一层结果才能最优，对吧。所以它具有最优子结构的性质。 那适合用动规解决的问题，还有一个特点就是， 无后效性，啊就是如果有一个问题满足无后效性的这种特点，你也可以考虑用动规来解决。什么叫无后效性啊？ 就是说当前的若干个状态，它的值一旦确定， 也就是说某一个子问题的值已经解决了， 当前的若干个状态值一旦确定，那此后的整个过程的衍变，就只跟这个若干个状态的值有关。 比如说这是一个状态，这个状态值已经确定了， 那后外面的事情怎么变化就只跟这个状态有关了，那至于之前， 由其他的状态如何演变到这种状态，可能有好多种选择，好多种手段好多种路径， 但不管用什么手段什么路径过来，对这个事情往后的演变都没有任何影响，后面的事情就只跟这个状态的值有关， 这种特性就叫做无后效性。 那总之一个问题，如果具有最优子结构性质， 或者说是它具有无后效性，那我们就可以考虑用动规来解决。
