DP最大子段和

动态规划处理“线”上的问题非常在行,今天我们就来探讨求解最大字段和的问题。 问题是这样的。 给定N个整数,要求求出最大的连续子段的和。 例如给定:1 -4 3 1 -2 其最大子段和为:4 该子段为:3 1 我们先来分析这个问题。我们最直观的方法就是穷举所有的子段并求和,找到其中最大的,即为答案,但是明显这样做,效率太低。题目中涉及到了“子段”,这使我们想到动态规划的通过寻找“最优子结构”来找到“最优解”的思路。 给定的N个数字存在数组A[N]当中,然后用B[N]来记录子段和的状态。读者可能有疑问,一个串的子串明显不会只有N个,那为什么只用N个元素来记录状态呢?这样做的原因正是因为我们使用动态规划的思路,B中存储的是状态,串中的每个数字的状态只考虑一次。 那么我们来考虑状态转移方程该如何构造: 假设我们已经得到了一个局部最大子串和B[K-1],考虑算上下一个元素A[K]的时候,这个子串的和为B[K] = B[K – 1] + A[K], 这里算出来B[K]如果大于或等于零,则一定有B[K

DP记忆化搜索

动态规划(dynamic programming)这个名词曾不止一次吓到我,而事实上,动态规划作为一种思想而非算法,其最大的作用是优化。这次笔记中,我就对最为经典的The Triangle[1]问题来对DP的记忆化搜索进行解释。 如图1,从三角形的最上面的顶点往下层走(每次只能向左或向右一个),那么如何走,才能途径的所有位置的点数之和最大呢? 第一种自然而然的思路就是把所有可能的路径都找到,并找到其中点数和最大的一条路径作为答案,然而这样的思路却存在着很大的效率问题,从第一个顶点开始往下走,每走一步都有2种选择,那么走到第N层的时候,路径数目就多达2^N条,枚举如此巨大数目的路径,必然会使程序在测试的过程中出现超时(TLE),所以这样的方法并不可取。 至此,我们可以隆重推出动态规划的思想了,我们从结果来看,答案的路径是确认的,那么第一步只有向左或向右才可能到达最终答案的地点,第二步也是,第三步也是……在这个过程中,我们往下走,只选择“能到达最优解”的路径走,这样就可以帮助我们减少大量的搜索