Oiclass P1235 题解

简单的一维动规

按照老师的要求

1. 划分阶段

非常容易的可以看出这道题目的阶段就是各个位置，即 \(i,\ j\) 。在这种划分下，每一种阶段的最优解可以由上一个阶段得到，且不会被右面的阶段所改变，故无后效性。综上，该题可以用 DP 求解

2. 确定状态和状态变量:

由 (1) 得：该题无后效性，故可用 递推的DP 进行求解，对于状态 \(i,\ j\) 的最优解，用 \(f_{i,j}\) 表示而 \(f_{i,j}\) 可由 \(a_{i,j}\) （输入的数组）及 \(f_{i - 1,j -1}\) 与 \(f_{i - 1,j}\) 得到

3. 确定决策井写出状态转移方程

通过 (2) 的分析，可以观察出状态状态转移方程如下： \[ f_{i,j} = \max(f_{i-1, j-1}\ ,\ f_{i -1, j}) + a_{i,j} \]

4. 边界条件

分析样例可以得到，递推的边界条件为： \[ f_{1, 1} =a_{1,1} \]

故，递推式为： \[ \begin{array}{lr} 当\ i,j\ ≥0:\\ F_{1,1} = a_{1,1}\\ F_{i,j}=a_{i,j} + \max(F_{i -1, j-1}\ ,\ F_{i -1, j}) \end{array} \]

5. 实现

实现可以直接模拟，代码如下

#include <iostream>

using namespace std;

int a[30][30], f[30][30],ans, n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            f[i][j] += max(a[i - 1][j - 1], a[i - 1][j]) + a[i][j];
            ans = max(ans, f[i][j]);
        }
    }
    cout << ans;
}

当然。也可以基于上面的思路及代码稍加优化，使得空间复杂度减半 ，同时代码更加简洁优雅。如下 ：

#include <iostream>

using namespace std;

int a[30][30], ans, n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
            a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
            ans = max(ans, a[i][j]);
        }
    }
    cout << ans;
}