定义状态：d(i,j) - 青岛理工大学.ppt

定义状态：d(i,j)表示从坐标为(i,j) 的位置出发到达最低行的最大和 根据定义的状态列出如下状态转移方程： d(i,j)=a(i,j) + max( d(i+1,j) , d(i+1,j+1) ) 分析一 使用回溯法，每次都有两个选择即左下或者右下。如果用回溯法求出所有可能的路线，从中选出和最的那条路线。遗憾的是这种方法的效率太低，来分析下这种算法的时间效率，由于从一个节点走到下一个节点有两种选择（左下，右下）。对于一个含有（n+1）层的数字三角形，路线有 2^n 条，也就是这种算法的时间效率为指数级的。 回溯法代码 #includestdio.h const int maxn = 100; int a[maxn][maxn],n; int max(int a,int b) { return ab?a:b; } int dfs(int i,int j) { if(i==n) return a[i][j]; return a[i][j]+max(dfs(i+1,j),dfs(i+1,j+1)); } int main() { int i,j; while(scanf(%d,n)!=EOF) { for(i=1;i=n;i++) { for(j=1;j=i;j++) { scanf(%d,a[i][j]); } } int ans=dfs(1,1); printf(%d\n,ans); } return 0;} 青岛理工大学选修课ACM第四小组团队 2016.3.30 动态规划基本原理 动态规划与分治方法类似，都是通过，划分子问题，求解子问题，根据子问题的解组合出原问题的解。但它们之间的差别在于： 分治方法： --将问题划分为互不相交的子问题，递归的求解子问题，然后组合出原问题的解。 动态规划： --动态规划应用于子问题重叠的情况，所谓子问题重叠就是指存在不同的子问题具有公共的子子问题。在子问题重叠的情况下分治算法会做很多不必要的工作，它会反复的求解那些相同的子子问题；而动态规划对每个子问题只求解一次，将其解保存在的数组中，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。 动态规划问题的特征： 动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。 1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。 设计动态规划法的步骤 1、找出最优解的性质，并刻画其结构特征； 2、递归地定义最优值（写出动态规划方程）； 3、以自底向上的方式计算出最优值； 4、根据计算最优值时得到的信息，构造一个最优解。 步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解 典型动态规划问题 拓扑排序 最小生成树（Prim算法和Kruskal算法） 关键路径 最短路径(dijkstra算法和floyd算法) …… 一个简单的问题 一个楼梯有n级，每次走一级或2级，从底到顶共有几种走法。 递推公式：f(n)=f(n-1)+f(n-2) 其中f(1)=1,f(2)=2 一个简单的例子 例如：当n＝6时，递归方法的解过程 f(5) f(4) f(3) f(2) f(2) f(1) f(3) f(2) f(1) f(4) f(3) f(2) f(2) f(1) f(6) 一个简单的例子 当n＝6时，动态规划方法的解过程 f(4) f(3) f(2) f(1) f(5) f(6) 动态规划常用技巧 顺推： 先计算小的子问题，再计算大的子问题。如刚才的斐波那契数列的求解过程。 动态规划常用技巧 递归实现 增加内存单元保存子问题的解，在递归求解的过程中判断子问题是否已经有解。有解，用之；无解，求之。 动态规划常用技巧 子问题编号 直接编号：用数组实现，适用于简单的子问题。 哈希编号：用哈希表记录子问题。 最短路径问题 问题: 两地之间是否有通路? 若存在多条通路，哪条路最短？ 最短路径问题 单源最短路径 Single-Source Shortest Path (Dijkstra算法) 所有顶点之间的最短路径问题 All-Pairs Shor