动态规划算法详解（C/C++）

动态规划

前言

在竞赛中，如果遇到动态规划的题目，只要不是经典题型，那么大概率就是以压轴题的形式出现。

用动态规划解决问题的步骤 (递推形式):

1. 定义状态表示：根据经验 + 需要的意义，赋予 dp 数组相应的含义（主要还是看需要记什么）。
2. 推导状态转移方程：在 dp 表中分析，当前格子如何通过其余格子推导出来的。
3. 初始化：将显而易见的以及边界情况下的位置填上值，来让后续填表的结果是正确的。
4. 确定填表顺序：根据状态转移方程，确定按照什么顺序来填表。
5. 找出最终结果：在表中找出需要的最终结果。

GESP 样题 六级 下楼梯 NOIP2010 提高组 乌龟棋

// 动态规划常要空间优化：即把不用了的值给不要了。但是背包问题如果不能用 1 个数组优化，而要多个数组的话，那就不空间优化了，否则可能会超时。
// 常见的优化方法：
// 方法一：一维转几个数
// 例题：GESP 样题 六级 下楼梯
// 方法二：二维转一维
// 1. 是否需要修改遍历顺序
// 2. 删掉一维即可
// 例题：USACO1.5 IOI1994 数字三角形 Number Triangles

最大子段和 NOIP2010 提高组 乌龟棋

一些技巧:

1. 状态表示: a. 研究子数组或子序列问题时，从某个位置结尾来定义状态表示。 例：最大子段和 b. 优化问题：有一维可以由其他维的数据推出的话，可以不要这一维 (不是指那个空间优化方法)。 例题：NOIP2010 提高组 乌龟棋
2. 状态转移方程: a. 求方案数一般是相加。 b. 常从最后一步开始分析去推导状态转移方程。
3. 初始化：在求方案数时，一般将第一个位置初始化为 1，其他位置为 0。

线性 dp

特点：状态转移只依赖于前一个或前几个状态；状态之间的关系是线性的。

路径类 dp

方格取数

走两次的得到的值之和最大问题：（两次的规则要一样，走到不同位置的得到的值不一样，且每位置的值只能得一次）。 例题：方格取数 在状态表示时：两者如果是同时出发的 (非同步则要改一点)，其横纵坐标之和会是一个定值。 一般表示为 f[st][i1][i2]：意思是：第一条路在 [i1,st-i1]，第二条路在 [i2,st-i2] 时，两者的路径（取数）之和最大。

经典线性 dp

经典线性 dp 问题有两个：最长上升子序列和最长公共子序列。 这两道题的解题思路，定义状态表示方式和推导状态转移方程的技巧常被用到其他题目中去。

最长上升子序列 (数据范围小时用此) 时间复杂度是 O(n^2)。 链接：最长上升子序列 要理解最长上升子序列是什么意思！！！

1. 状态表示：dp[i] 表示：以 i 位置为结尾的所有子序列中，最长递增子序列的长度。
2. 状态转移方程：根据子序列的构成方式进行分类讨论： 第一种：子序列长度为 1：此时的 dp[i] = 1; 第二种：子序列的长度大于 1：设 j 为前面某一个数的下标，只要 a[j]<a[i]，i 位置元素跟在 j 元素后面就可以形成递增序列，其 dp[i] = max(dp[j]+1, dp[i])。
3. 初始化：每次填表的时候，先把这个位置的数改成最小的域值即可。

主要部分的代码展示:

int ret = 0;
for(int i=1;i<=n;i++) {
    dp[i]=1;
    for( j=;j<i;j++) {
        (a[j]<a[i]) dp[i] = (dp[i],dp[j]);
    }
    ret = (ret,dp[i]);
}