Chapter6(4)_N皇后(回溯法).ppt

回溯回溯BacktrackingBacktracking回溯N皇后问题跳马问题迷宫问题图的着色问题0-1背包问题装载问题批处理作业调度填数问题组合输出问题算24点问题ACM应用学习要点v掌握回溯的概念掌握回溯的概念v掌握经典问题的回溯解决方法掌握经典问题的回溯解决方法v掌握回溯与其它方法的异同掌握回溯与其它方法的异同►有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法►回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法这种方法适用于解一些组合数相当大的问题►回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索回溯法回溯算法是所有搜索算法中最为基本的一种算法,是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索算法思想：算法思想：采用了一种“走不通就掉头走不通就掉头”的思想搜索时往往有多分支，按某一分支为新的出发点，继续向下探索，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。

回溯法回溯算法是所有搜索算法中最为基本的一种算法,是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索回溯法搜索的方式搜索的方式       主要采用深度优先搜索的方式回溯三要素：回溯三要素：     1) 解空间：该空包含问题的解     2) 约束条件     3) 状态树问题的解空间•问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式•显约束：对分量xi的取值限定•隐约束：为满足问题的解而对不同分量之间施加的约束•解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）n=3时的0-1背包问题用完全二叉树表示的解空间生成问题状态的基本方法►扩展结点:一个正在产生儿子的结点称为扩展结点►活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点►死结点:一个所有儿子已经产生的结点称做死结点►深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）►宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点►回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。

具有限界函数的深度优先生成法称为回溯法回溯法的基本思想(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间在任何时刻，算法只保存从根结点到当前扩展结点的路径如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法void backtrack (int t){ if (t>n) output(x); else for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) backtrack(t+1); }}迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。

void iterativeBacktrack (){ int t=1; while (t>0) { if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else t++;} } else t--; }}在一个n*n的国际象棋棋盘上放置n个皇后，使得它们中任意2个之间都不互相“攻击”，即任意2个皇后不可在同行、同列、同斜线上输出N，⑴求N皇后问题的一种放法；⑵求N皇后问题的所有放法分析：分析： N=4时，右图是一组解时，右图是一组解要素一： 解空间一般想法：利用二维数组，用[i,j]确定一个皇后位置！优化：利用约束条件，只需一维数组即可！           x:array[1..n] of integer;           x[i]：i表示第i行皇后                   x[i]表示第i行上皇后放第几列x[3,1,4,2]N皇后问题要素二：约束条件不同行：数组x的下标保证不重复不同列：x[i]<>x[j]    (i<=I,j<=n；i<>j)不同对角线：abs(x[i]-x[j])<>abs(i-j)要素三：状态树将搜索过程中的每个状态用树的形式表示出来！画出状态树对书写程序有很大帮助！填到第填到第K行时，就与前行时，就与前1~(K-1)行都进行比较行都进行比较Function Place(k:integer):boolean; place:=true; for j←1 to k-1 do if |k-j|=|x[j]-x[k]| or x[j]=x[k] then place:= falseN皇后问题K=0K=1*** ****** * ** * *回溯**** ******回溯** *********K=3K=2K=4****出解后可以继续刚才的做法过程：过程：进入新一行，该行上按顺序逐个格子尝试，直到能放为止（不冲突、不越界）算法描述：1.产生一种新放法2.冲突，继续找，直到找到不冲突----不超范围3.if 不冲突 then   k0 do begin x[k] ← x[k] +1 while x[k]<=n and (not place(k)) do x[k] ← x[k] +1 if x[k]<=n then if k=n then sum ← sum+1 else begin k ← k+1 x[k] ← 0 end else k ← k-1 end end 非递归写法：非递归写法： if k=n then print;flag ←false算法描述：1.产生一种新放法2.冲突，继续找，直到找到不冲突----不超范围3.if 不冲突 then   k

    请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走到右上角（n，m）输入：9 5输出：(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)跳马问题跳马问题分析：分析：按题意，马每一步可以有4种走法！搜索过程：搜索过程：1.当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1AA1A22.当到达A1点后，又有三条线路可以  选择，于是再任意选择一条，到达B13.从B1再出发，又有两条线路可以选择，先选一条，到达C1AA1A2B1B2B3C1C2跳马问题跳马问题AA1A2B1B2B3C1C2D1D2D3E14.  从C1出发，可以有三条路径，选择D1但到了D1以后，我们无路可走且D1也不是最终目标点，因此，选择D1是错误的，我们退回C1重新选择D2同样D2也是错误的再回到C1选择D3D3只可以到E1，但E1也是错误的返回D3后，没有其他选择，说明D3也是错误的，再回到C1此时C1不再有其他选择，故C1也是错误的，退回B1，选择C2进行尝试AA1A2B1B2B3C2E2BD4E1F15.  从C2出发，有四条路径可以选择，选择D4，从D4出发又有两条路径，选择E1错误，返回D4选择E2，从E2出发有两条路径，先选择F1错误，返回E2选择B，而B恰好是我们要到达的目标点，至此，一条路径查找成功。

跳马问题跳马问题①①②②③③④④从上面的分析我们可以得知：从上面的分析我们可以得知：       在无法确定走哪条线路的时候，任选一条线路进行尝试；为方便路径表示，对马可以走到的四个点（方向）都编上号；       当从某点出发，所有可能到达的点都不能到达终点时，说明此点是一个死节点，必须回溯到上一个点，并重新选择一条新的线路进行尝试解空间:       为了描述路径，我们最直接的方法就是记录路径上所有点的坐标优化：优化：每一个方向上两个坐标和原位置对应关系若马所处的位置为(x,y)，则其下一步可以到达的四个位置分别是(x+1, y-2)，(x+2, y-1)，(x+2, y+1)，(x+1, y+2)增量数组：dx = (1, 2, 2, 1)dy = (-2, -1, 1, 2)方向t，下一步的位置就是(x+dx[t], y+dy[t])xypath:array[1..m] of integer;其中，path[i]：表示第i个节点所走的方向跳马问题跳马问题约束条件：不越界： (x + (x + dx[idx[i] <= n) and (y + ] <= n) and (y + dy[idy[i] > 0) and (y + ] > 0) and (y + dy[idy[i] <= n)] <= n) 状态树：0①②③④⑤⑤⑤⑥④Path[1]:=3Path[2]:=2Path[3]:=3Path[4]:=234Path[5]:=14①②③④④⑤⑤⑤⑤⑥⑥⑦⑦①①②②③③④④算法描述：1.产生一种新走法2.越界，继续用新走法，直到找到一种走法不越界----不超过4种走法3.if  不越界  then   km) and (y<>n) do begin path[k] ←path[k] +1 while (x + dx[i] <= n) and (y + dy[i] > 0) and (y + dy[i] <= n) and (path[k]<=4) do path[k] ← path[k] +1 if path[k]<=4 then{在在4种走法中找到不越界的走法种走法中找到不越界的走法} begin x ←x+dx[i]，，y ←y+dy[i] if (x<>m) and (y<>n) then print else begin k ← k+1 path[k] ← 0 end end else path[k] ← 0，，k ← k-1 end end 跳马问题（非递归）跳马问题（非递归）跳马问题跳马问题跳马问题（递归）跳马问题（递归）跳马问题跳马问题procedure search(k: integer); // 递归查找begin for i := 1 to 4 do // 依次尝试四个方向 if (x + dx[i] <= n) and (y + dy[i] > 0) and (y + dy[i] <= n) then // 在棋盘上 begin path[k] := i; // 记录下当前方向 x := x + dx[i]; y := y + dy[i]; // 修改扩展节点坐标 if (x = n) and (y = m) then // 是否是目标点 begin output(k); halt; // 是目标点，输出结果并终止程序 end else search(k+1); // 不是目标点，继续尝试下一步 // 扩展出的点是死点，回溯 x := x - dx[i]; y := y - dy[i]; // 恢复扩展节点坐标，状态恢复 end;end;BeginBegin read(n,m); read(n,m); x:=1; y:=1; x:=1; y:=1; search(1); search(1);End.End.思考:1.  在本例中，我们只要求输出一条可行路径，如果我们需要输出所有的可行路径，怎样改动此程序呢？<递归><非递归>2.  如果我们把问题改成“在n×m的棋盘上有一骑士，开始时，骑士在点(x,y)，现在请你找出一条可行的路径，使得骑士可以不重复的走遍棋盘上的每一个点。

的话，又要如何编写此程序呢？跳马问题跳马问题       设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角，迷宫格子中分别放有0和1，0表示可走，1表示不能走，迷宫走的规则如图当迷宫给出之后，找出一条从入口到出口的通路输入：N          N*N的迷宫输出：具体路径输入样例：       80001101010110110010010010011010101000110011111010011101111000000输出样例：(1,1)-(2,1)-(3,1)-(2,2)-(1,3)-(2,4)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1)迷宫问题迷宫问题0001101010110110010010010011010101000110011111010011101111000000xy①①②②③③④④⑤⑤⑥⑥⑦⑦⑧⑧分析：分析：3.增量和方向表示       dx=(1,1,-1,-1,1,-1,0,0)       dy=(-1,0,1,0,1,-1,1,-1)path:array[1..maxn*maxn] of integer;其中，path[i]：表示第i个节点所走的方向解空间约束条件不越界且该点可走(x>=1) and (x<=N) and (y>=1) and (y<=N) and A[x,y]=11.迷宫信息用二维数组表示        A:array[1..maxn,1..maxn] of 0..1;2.入口（1,1）；出口（n,1）状态树迷宫问题迷宫问题给定无向连通图G和m种不同的颜色。

用这些颜色为图G的各顶点着色，每个顶点着一种颜色是否有一种着色法使G中每条边的2个顶点着不同颜色这个问题是图的m可着色判定问题若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数求一个图的色数m的问题称为图的m可着色优化问题图的着色问题图的着色问题       有形如下列图形的地图，图中每一块区域代表一个省份，现请你用红（1）、兰（2）、黄（3）、绿（4）四种颜色给这些省份填上颜色，要求每一省份用一种颜色，且任意两个相邻省份的颜色不能相同，请给出一种符合条件的填色方案1 12 23 34 45 56 67 7图的存储图的存储R:array[1..n,1..n] of 0..1;其中，R[I,j] =0------省i和省j不相邻                   =1------省i和省j相邻①①②②③③④④⑤⑤⑥⑥⑦⑦将实际地图用无向图的形式给出，每个省份代表图上的一个顶点，边代表两个省份是相邻的0100001101111101010000110100010101001001001100010四色问题图的着色问题图的着色问题•解向量：(x1, x2, … , xn)表示顶点i所着颜色x[i] •可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。

void Color::Backtrack(int t){ if (t>n) { sum++; for (int i=1; i<=n; i++) cout << x[i] << ' '; cout << endl; } else for (int i=1;i<=m;i++) { x[t]=i; if (Ok(t)) Backtrack(t+1); }}bool Color::Ok(int k){// 检查颜色可用性 for (int j=1;j<=n;j++) if ((a[k][j]==1)&&(x[j]==x[k])) return false; return true;}复杂度分析复杂度分析图m可着色问题的解空间树中内结点个数是对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)因此，回溯法总的时间耗费是图的着色问题图的着色问题1 12 23 34 45 56 67 7算法思想：算法思想：从编号1的省开始，按4种颜色的排列顺序，首先选择第一种颜色，然后检查是否矛盾，即相邻的区域中是否已有该颜色，若不矛盾，则涂色，若矛盾，则选择下一个颜色，再判断，当4种颜色都不可能时，则需回溯。

当第一个省的颜色确定之后，依次对第二个省、第三个省……进行处理，当所有省都涂上颜色之后，得到一种解法color:array[1..maxn] of integer;其中，color[k]：表示第k个省所填的颜色解空间Color(1,2,1,3,1,3,4)迷宫问题迷宫问题Function pd(k:integer):boolean;Var m:integer;Begin m:=1; {从第一个省份开始检查是否冲突} pd:=true; {不冲突} while (m < k) and (color[k] * g[m, k] <> color[m]) do inc(m); if k>=m then pd:=false; {冲突}End;约束条件该点k涂的颜色(color[k)与和k相邻的点m(1<=m<=k-1)的颜色(color[m])相同color[k] * g[m, k] =color[m]状态树迷宫问题迷宫问题procedure search(k: integer); {递归搜索第m个省份}begin if k > n then {是否所有省份都已经填色} begin write(color[1]); { 已全部填色，输出结果，终止程序} for j := 2 to n do write(' ', color[j]); writeln; halt end else {还未全部填色} for j := 1 to 4 do begin {依次用四种颜色对当前省份填色} if (k <= n) and pd(k) then {没有冲突} begin color[k] := j; { 记录当前省份颜色} search(k + 1); {递归检查下一个省份} end; end;end;四色问题（递归）四色问题（递归）迷宫问题迷宫问题输入：第一行一个整数，为背包的容量M；第二行一个整数，为物品的种数Ｎ；第三行Ｎ个整数为各物品的重量；第四行Ｎ个整数分别为Ｎ个物品的价值输出：第一行为最大总价值；第二行为装入的各物品的重量（未装的物品用０）；第三行为装入的各物品的价值 （未装的物品用０）       已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。

若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大输入样例： 50 3 10 20 30 60 100 120输出样例： 220 0 20 30 0 100 120测试数据：输入： 10 5 2 2 6 5 4 6 3 5 4 6输出： ?0-10-1背包问题背包问题bag:array[1..maxn] of 0..1;其中，bag[k]=1表示第k个物品要取          0表示第k个物品不取解空间约束条件第k个物品确定放置方法后，背包所剩重量足够放第K个物品wei-bag[k]*w[k]>=0{wei：背包还能装的重量}Best:=0;   表示最大价值当一组解产生后，得到当前总价值count，if count>best then best:=count利用这种方法记录最优解！如果还要记录最优时的物品取法应：if count>best then begin     best:=count;     for i:=1 to n do y[i]:=bag[i];状态树求最优值求最优值0-10-1背包问题背包问题2.本题可以用递归求解：1.本题可用方法很多！非递归写法与前几题相似，请自己写出！算法分析：算法分析：       设当前有N个物品，容量为M；       这些物品要么选，要么不选，我们假设选的第一个物品编号为i（1~i-1号物品不选），问题又可以转化为有N-I个物品（即第I+1~N号物品），容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可。

回溯（状态恢复）后，需恢复的状态有：ØBag[k] Ø背包可装的物品重量：wei:=wei+w[k]*iØ已装物品的价值总和：count:=count:-c[k]*i0-10-1背包问题背包问题procedure work(k,wei:integer);    var i,j:integer;    begin      for i:=1 downto 0 do          if  (wei-w[k]*i>=0) then             begin                bag[k]:=i;                count:=count+c[k]*i;                if (k=n) and (count>best) then                   begin                      best:=count;                      for j:=1 to n do y[j]:=bag[j];                   end;                if k

如果有，找出一种装载方案容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近由此可知，装载问题等价于以下特殊的0-1背包问题用回溯法设计解装载问题的O(2n)计算时间算法在某些情况下该算法优于动态规划算法装载问题装载问题•解空间：子集树•可行性约束函数(选择当前元素)：•上界函数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r当前最优载重量bestwvoid backtrack (int i) {// 搜索第i层结点 if (i > n) // 到达叶结点 更新最优解bestx,bestw;return; r -= w[i]; if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { x[i] = 0; // 搜索右子树 backtrack(i + 1); } r += w[i]; }装载问题装载问题给定n个作业的集合{J1,J2,…,Jn}。

每个作业必须先由机器1处理，然后由机器2处理作业Ji需要机器j的处理时间为tji对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小t tji ji机器机器1 1机器机器2 2作业作业1 12 21 1作业作业2 23 31 1作业作业3 32 23 3这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19易见，最佳调度方案是1,3,2，其完成时间和为18批处理作业问题批处理作业问题•解空间：排列树void Flowshop::Backtrack(int i){ if (i > n) { for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestf = f; } else for (int j = i; j <= n; j++) { f1+=M[x[j]][1]; f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2]; f+=f2[i]; if (f < bestf) { Swap(x[i], x[j]); Backtrack(i+1); Swap(x[i], x[j]); } f1- =M[x[j]][1]; f- =f2[i]; }}class Flowshop { friend Flow(int**, int, int []); private: void Backtrack(int i); int **M, // 各作业所需的处理时间 *x, // 当前作业调度 *bestx, // 当前最优作业调度 *f2, // 机器2完成处理时间 f1, // 机器1完成处理时间 f, // 完成时间和 bestf, // 当前最优值 n; // 作业数}; 批处理作业问题批处理作业问题【【问题描述问题描述】】        从整数1到10中任取9个不同的数，填入下面的9个格子中，使所有相邻（左、右、上、下）两个格子中的数的和是素数。

输出输出】】 一行3个数，共3行样例样例】】 1    2    54    3    87   10   9【【说明说明】】 输出所有本质不同的解通过某个解的旋转、上下翻转、左右翻转得到的是本质相同的）填数问题填数问题【【问题描述问题描述】】       排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r<＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数       现要求你不用递归的方法输出所有组合       例如n＝5，r＝3，所有组合为： 1 2 3 1 2 4    1 2 5    1 3 4   1 3 5    1 4 5    2 3 4    2 3 5    2 4 5    3 4 5【【输入输入】】一行两个自然数n、r(1

您作为游戏者将得到4个1~9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24       您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）下面我们给出一个游戏的具体例子：       若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3*7=24输入输入】】       只有一行，四个1到9之间的自然数输出输出】】 如果有解的话，只要输出一个解，输出的是三行数据，分别表示运算的步骤其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“=24”如果两个操作数有大小的话则先输出大的       如果没有解则输出“No answer!”【【输入样例输入样例】】 【【输出样例输出样例】】1 2 3 72+1=37*3=2121+3=24算算2424点问题点问题v优先得方式求解优先得方式求解 可本质上都是及时得淘汰不合适的解可本质上都是及时得淘汰不合适的解 我以为只是表现的形式不同我以为只是表现的形式不同 本本质上是一样的质上是一样的 个人意见个人意见 供大家讨论供大家讨论 --------------------------------------------------------------- 这本来就是两个完全不同的领域，一个是算法领域，一个是数据结构问题。

两者又交这本来就是两个完全不同的领域，一个是算法领域，一个是数据结构问题两者又交叉，又有区别从本质上讲就是算法与数据结构的本质区别，回朔是一个具体的算法，叉，又有区别从本质上讲就是算法与数据结构的本质区别，回朔是一个具体的算法，动态规划是数据结构中的一个概念动态规划讲究的是状态的转化，以状态为基准，动态规划是数据结构中的一个概念动态规划讲究的是状态的转化，以状态为基准，确定算法；回朔讲究过程的推进与反还，随数据的搜索、标记，确定下一步的行进方确定算法；回朔讲究过程的推进与反还，随数据的搜索、标记，确定下一步的行进方向先说到这里，有点晕，不足之处多多指教先说到这里，有点晕，不足之处多多指教 --------------------------------------------------------------- 其实根本是不同的，其实根本是不同的， 回朔是去搜索，而动态规划，是从小单元开始积累计算结果回朔是去搜索，而动态规划，是从小单元开始积累计算结果 前一个从根出发，后一个是从枝叶出发前一个从根出发，后一个是从枝叶出发 普通，如果想要搜索时，发现有很多重复计算，就应该想到用动态规划了普通，如果想要搜索时，发现有很多重复计算，就应该想到用动态规划了 不过，有时高手可以把更本没有关联的问题都用动态规划解决不过，有时高手可以把更本没有关联的问题都用动态规划解决 他能找到很抽象的几个他能找到很抽象的几个“阶段阶段”！！ 。