《数字三角形精编版》由会员分享，可在线阅读，更多相关《数字三角形精编版（9页珍藏版）》请在金锄头文库上搜索。
1、数字三角形 给你一个数字三角形 形式如下 12345678910找出从第一层到最后一层的一条路 使得所经过的权值之和最小或者最大 分析 你会立刻发现这是一个动态规划的决策问题 每次有两种选择 向左和向右 一个n层的数字三角形完整路线有2 n条 所以当n比较大的时候 用回溯法是行不通滴 如果用d i j 为从格子 i j 出发时得到的最大和 包括格子 i j 本身 那么可以得到状态转移方程 d i j a i j max d i 1 j d i 1 j 1 递归计算 有了状态转移方程就好办了 intdp inti intj if i n returnd i j a i j elsereturnd
2、 i j max dp i 1 j dp i 1 j 1 重叠子问题 这样做是正确的 但是时间效率太低 其原因在于重复计算 1 1 2 1 2 2 3 1 3 2 3 2 3 3 4 1 4 2 4 2 4 3 4 2 4 3 4 3 4 4 记忆化搜索 显而易见 这个算法就是最简单的搜索算法 时间复杂度为2n 明显是会超时的 分析一下搜索的过程 实际上 很多调用都是不必要的 也就是把产生过的最优状态 又产生了一次 记忆化搜索 记忆化搜索把程序分成两部风 首先把d数组初始化为 1 intdp inti intj memset d 1 sizeof d if d i j 0 returnd i
3、j elseif i n returnd i j a i j elsereturnd i j a i j max dp i 1 j dp i 1 j 1 时间复杂度为n 2 记忆化的功效 动态规划的实质 可以看出动态规划的实质就是这也就是为什么我们常说动态规划必须满足重叠子问题的原因 记忆化 正符合了这个要求 记忆化搜索 递推计算 因为在计算d i j 前 它所需要的d i 1 j 和d i 1 j 1 一定已经计算出来了 for i 1 i 1 i for j 1 jd i 1 j 1 d i j a i j d i 1 j elsed i j a i j d i 1 j 1 END POJ1163POJ2760
