一、动态规划是什么在解决复杂问题时暴力枚举法常常因为时间复杂度过高而导致程序效率低下。与此不同的是动态规划DP提供了一种更加高效的方式——通过把原问题拆解为相对简单的子问题状态将原本需要反复计算的情况记录下来以便在下一次遇到同一个子问题时直接查表从而达到优化的效果。通常来说使用动态规划解决问题需要定义清楚状态、状态转移方程和边界情况下面是动态规划的两大核心性质它们可以帮助我们判断这道题目是否可以利用动态规划来解决最优子结构全局最优解包含子问题的最优解无后效性子问题决策不影响后续状态的定义方式二、线性 DP线性 DP 属于 DP 中最常见的一种其状态转移是线性化的第 i 个状态只依赖于前面若干个状态。定义清楚状态并且找到状态之间的依赖关系是解决问题的关键。下面以一道题目为例说明题目链接: linkP1115 最大子段和题目描述给出一个长度为n nn的序列a aa选出其中连续且非空的一段使得这段和最大。输入格式第一行是一个整数表示序列的长度n nn。第二行有n nn个整数第i ii个整数表示序列的第i ii个数字a i a_iai。输出格式输出一行一个整数表示答案。输入输出样例 #1输入 #17 2 -4 3 -1 2 -4 3输出 #14说明/提示样例 1 解释选取[ 3 , 5 ] [3, 5][3,5]子段{ 3 , − 1 , 2 } \{3, -1, 2\}{3,−1,2}其和为4 44。数据规模与约定对于40 % 40\%40%的数据保证n ≤ 2 × 10 3 n \leq 2 \times 10^3n≤2×103。对于100 % 100\%100%的数据保证1 ≤ n ≤ 2 × 10 5 1 \leq n \leq 2 \times 10^51≤n≤2×105− 10 4 ≤ a i ≤ 10 4 -10^4 \leq a_i \leq 10^4−104≤ai≤104。三、算法原理本题要求解的是一段序列的最大子段和通过暴力枚举法枚举序列的左右端点我们可以很轻松地得出正确答案但是非常遗憾这种解法即使通过前缀和的优化也只是到达了 O(n^2)1e10 级别的数据量将会超时。经过观察原问题可以被拆解为以 a[i] 结尾的最大子段和状态这样最终问题就变成了在所有数的最大子段和中选取最大的那一个结果。在以 a[i] 为结尾的最大子段和中要么取之前最大子段和的结果和 a[i] 合并要么清空最大子段和的结果保留 a[i]满足无后效性。状态定义设 f[i] 表示以第 i 个数结尾的连续子段的最大和。状态转移方程f[i] max(f[i - 1] a[i], a[i])含义以a[i]结尾的最大子段要么是把a[i]接到前面以a[i-1]结尾的最大子段后面如果前面的和是正贡献要么是a[i]自己单独成段如果前面的和是负贡献不如舍弃。边界条件f[1] a[1]。代码实现#includeiostreamusingnamespacestd;constintN2e510;intf[N];inta[N];intmain(){intt;cint;for(inti1;it;i)cina[i];f[1]a[1];for(inti1;it;i){f[i]max(f[i-1]a[i],a[i]);}intret-0x3f3f3f3f;//结果有可能是负数所以要足够小for(inti1;it;i)retmax(ret,f[i]);coutretendl;return0;}手动模拟样例序列2 -4 3 -1 2 -4 3ia[i]f[i] max(f[i-1]a[i], a[i])ans12222-4max(2-4, -4) -2233max(-23, 3) 334-1max(3-1, -1) 2352max(22, 2) 446-4max(4-4, -4) 0473max(03, 3) 34最终答案为4与样例输出一致。对应子段是[3, -1, 2]下标 3~5。时间复杂度为 O(n)只需遍历一次序列。
