38动态规划.pptx

动态规划 经典问题---数塔问题 有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如下图所示。从第一行的数开始，每次可以往左下或右下走一格，直到走到三角形底层，把沿途经过的数全部加起来作为得分。如何走，使得这个得分最大？ 经典问题---数塔问题 这是一个决策问题：每次选一个方向（左/右）行走。到底朝哪个方向走，取决于从左走能取到最大值还是从右走能取到最大值。 最容易想到的是贪心算法：每次选择数字较大的方向走。 1----3---10----3，错误 贪心法在此问题无法保证得到最优解。 经典问题---数塔问题 暴力有哪些信誉好的足球投注网站，列举出所有可能的路径再比较，得出和最大的路径。 int d[100][100],n; int dfs(int x,int y)//x,y数组下标，函数返回从d[x][y]开始走到最后一层的最大和 { if(x==n)//边界条件 { return d[x][y]; } else { int left=dfs(x+1,y);//从左下方的数字开始能够得到的最大和 int right=dfs(x+1,y+1);//右下方能得到的最大和 return d[x][y]+max(left,right); } }//main函数内调用dfs(1,1) 经典问题---数塔问题 暴力有哪些信誉好的足球投注网站存在大量重复计算 在有哪些信誉好的足球投注网站的过程中以（3,2）为起点的子树有哪些信誉好的足球投注网站了两次。 1 3 2 4 10 1 4 3 2 20 经典问题---数塔问题 记忆化有哪些信誉好的足球投注网站，记忆数组f[x][y]存储(x,y)到数塔底层最大值，默认全为0 int d[100][100],n,f[100][100]; int dfs(int x,int y) { if(x==n) { return d[x][y]; } else if(f[x][y]!=0)return f[x][y]; else { int left=dfs(x+1,y); int right=dfs(x+1,y+1); f[x][y]=d[x][y]+max(left,right); return f[x][y]; } } 递推计算f[][] 假设以格子(i,j)为首的“子三角形”的最大和为f[i][j] ，则原问题的解是f[1][1]。 从格子(i,j)出发往左走和往右走将分别到达位置(i+1,j)和(i+1,j+1)，则： f[i][j]=d[i][j]+max(f[i+1][j],f[i+1][j+1]); f[1][1]=1+max(f[2][1],f[2][2]); f[2][1]=3+max(f[3][1],f[3][2]); f[2][2]=2+max(f[3][2],f[3][3]); 递推计算 从最底层开始，层层递进，最后得到最大值。 时间复杂度为O(N^2) 实际上d数组和f数组可以合并 int i , j; for(j = 1;j= n; j++)f[n][j] = d[n][j];//最后一层 for(i = n-1;i= 1;i--)//倒数第二层往上 for(j = 1;j=i;j++) f[i][j]=d[i][j]+max(f[i+1][j],f[i+1][j+1]); 另一种递推方式： f[i][j]表示从d[1][1]到达d[i][j]能够得到的路径总和的最大值，从左上方(i-1,j-1)和右上方(i-1,j)到达(i,j)则： d[i][j]+max(f[i-1][j-1],f[i-1][j]) 1ji f[i][j]= d[i][j]+f[i-1][j]; j=1 d[i][j]+f[i-1][j-1]; j=i 从上往下计算，取max(f[n][i]),1=i=n 动态规划原理 在求解一个具体问题时，问题可以按时间顺序分解成若干相互联系的有顺序的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列，要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。 多阶段决策问题 现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图所示，试找出从结点1到结点10的最短路径。 多阶段决策问题 第一阶段 第二阶段 第三阶段 第四阶段 第五阶段 F[i]表示结点i离结点10的最短距离 那么，有F[i]=min(map[i][j]+F[j]),i-j存在有向边 最后，求F[1] F[7]=3, F[8]=4, F[9]=6 F[4]=6+F[9], F[5]=min(7+F[7],5+F