动态规划基础概念

动态规划（Dynamic Programming，dp）是一类用来解决最优化问题（和部分计数问题）的算法。动态规划的学习和题目从普及组到 IOI 都会出现。

动态规划可解问题的特点

如果一个问题可以通过动态规划求解，则这个问题一定（充分不必要）满足这两个特点：

最优子结构

动态规划可以解决的问题通常是求问题最优解的问题。且这种问题可被分割为多个子问题，子问题的解也是最优的。通过各个子问题的最优解可以逐步计算出全局最优解，得出答案。

无后效性

动态规划划分出的子问题有以下性质：某个子问题的结果被求解之后，其值不会受如何求解影响。后面的计算如果可以用到这个子问题的结果，则和这个子问题通过怎样的方法怎样的顺序求解无关，即“未来和过去无关”。

动态规划的基本步骤

找子问题，把问题划分为各个阶段。
根据阶段划分确定动态规划的状态。
找到初始状态。
通过阶段之间的决策找出状态转移方程。
通过状态转移方程，通过递推或者记忆化搜索写出代码、优化，求出问题的解。

这些步骤看上去比较抽象，下面通过几个例题来熟悉一下这些步骤。

例题

洛谷 P1216 [IOI1994] 数字三角形 Number Triangles

这题是动态规划最典型的入门题，完美满足动态规划可解问题的两个性质。而且 IOI（国际信息学奥林匹克竞赛）作为 OI 最高峰，考动态规划基本题是因为那时候动态规划刚被发明，所以这题极适合入门学习。

先分析这个问题：

最优子结构：显然这个问题可以划分成多个子问题，每个子问题求解出从起点出发走到某个数字的最优解，问题最终的答案是最后一行每个数字对应的子问题的解的最大值，可以通过子问题的最优解计算而来。
无后效性：到达每个数字的最大值只和到达其上一层两个点得到的最大值有关，和上一层两个点的最大值是从哪转移来的无关。

因此，这个问题可以通过动态规划求解，解决步骤：

子问题：dp[i][j] 表示走到第 i 行第 j 个数时子问题的答案，将其定义为状态。
初始状态：显然 dp[1][1]=a[1][1]，将其作为初始状态。
决策：每个数可以从他上面两个数走来，所以状态转移方程： dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]。
根据状态转移方程写出代码，最终答案是 max(dp[n][1...n])。

下面我们看如何写出代码：

在转移过程中，用每个已经计算出的状态计算当前的新状态，代码实现如下：

#include <bits/stdc++.h>
using namespace std;
// #define int long long

int n;
int a[1005][1005], dp[1005][1005];

signed main() {
    ios::sync_with_stdio(0);
    #ifdef DEBUG
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif

    // Don't stop. Don't hide. Follow the light, and you'll find tomorrow. 

    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= i;j++) {
            cin >> a[i][j];
        }
    }
    dp[1][1] = a[1][1];
    for (int i = 2;i <= n;i++) {
        for (int j = 1;j <= i;j++) {
            if (j == 1) dp[i][j] = dp[i - 1][j] + a[i][j];
            else if (j == i) dp[i][j] = dp[i - 1][j - 1] + a[i][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
            // 状态转移，根据状态转移方程，注意边界条件
        }
    }

    int ans = 0;
    for (int i = 1;i <= n;i++) ans = max(ans, dp[n][i]);
    cout << ans << endl;

    #ifdef DEBUG
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
    #endif
    return 0;
}

JZTXT

【动态规划】动态规划基础、背包 dp 学习笔记