数字三角形模型

母题-摘花生

Y式DP-集合角度

状态表示
- 集合
  所有从\((1,1)\)走到\((i,j)\)的方案
- 属性
  \(所有方案里的最大值\)
集合划分
\((i,j)一定是从(i-1,j),(i,j-1)两步中转移而来\)

转移方程代码

时间复杂度\(O(n^2)\)

for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        f[i][j] = max(f[i-1][j],f[i][j-1]) + w[i][j];

优化

从转移方程来看，我们每次只用到了本层和上一层的数据，因此我们可以采用滚动数组来进行空间上的优化

f[2][N], w[2][N];
for (int i = 1; i <=n; ++i)
    for (int j = 1; j <= n; ++j)
    {
        cin >> w[i&1][n];
        f[i&1][j] = max(f[i&1][j-1], f[(i-1)&1][j]) + w[i&1][j];
    }
cout <


扩展题目
最低通行费
本题相比与摘花生题目多了一个限制条件，要求在\(2N-1\)的时间内达到\((n,m)\)，结合曼哈顿距离可以得知，要求每一步都是能够减小曼哈顿距离的，达到最短路的一个效果，那每一步的选择必定是朝右或者朝下行走，即满足摘花生模型。

曼哈顿距离：两个点在坐标轴上的绝对值，即\(d = |x1-x2|+|y1-y2|\)

DP

状态表示

集合意义

所有从\((1,1)\)走到\((i,j)\)的方案数
属性

方案数的最小值


集合划分

以最后一步划分， \((i,j)一定是从(i-1,j),(i,j-1)两步中转移而来\)

Code
本题不同的地方在于DP的初始化和边界问题，需要特判\((1,1)\)，同时因为是取最小值，所以需要初始化为\(INF\)。
memset(f, 0x3f, sizeof f); //初始化
f[1][1] = w[1][1];
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) 
        f[i][j] = min({f[i][j], f[i-1][j] + w[i][j], f[i][j-1] + w[i][j]});

方格取数
区别
走两次，并取两次所取数之和的最大值。
错误思路
一个贪心的想法是走两次，每次都是依据当前情况来取最优解，两个最优解相加就是答案，但其实是不行的，第二次DP的结果其实是在第一次DP产生后续影响的前提下完成的一个局部最优，不满足无后效性，所以两次局部最优无法推出整体最优解，得到的是一个最优解的近似值。
正确思路
同时走，从\((1,1),(1,1)\)走到\((n,n),(n,n)\)，那么两次DP得到的结果都是根据当前地图得到的答案，且冲突的点——重复经过的点可以被解决。
DP

状态表示 (f[k][i1][i2])

集合定义

同时从\((1,1)(1,1)\)走到\((i1,k-i1)(i2,k-i2)\)的所有路径
属性

MAX


状态计算（四个状态取MAX）

右行+右行

\(f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2]+t)\)
右行+下行

\(f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2-1]+t)\)
下行+右行

\(f[k][i1][i2] = max(f[k][i1-1][i2],f[k-1][i1][i2]+t)\)
下行+下行

\(f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2-1]+t)\)



相关状态解释

k的说明

\(k = i_1+j_1=i_2+j_2\)

\(当二者的k相同的时候，二者可能相交于一点\)
t的说明

\(i_1 ==i_2,k-i_1==k-i_2，说明此时同时走到同一个点上，t=w[i1][j1],否则t=w[i1][j1] + w[i2][j2]\)

Code
for (int k = 2; k <= n; ++k)
    for (int i1 = 1; i1 <= n; ++i1)
        for (int i2 = 1; i2 <= n; ++i2 )
        {
            int j1 = k-i1, j2 = k - i2;
            int t = (i1 == i2 && j1 == j2 ? w[i1][j1] : w[i1][j1] + w[i2][j2);
            int& x = f[k][i1][i2];
            x = max(x, t + f[k - 1][i1 - 1][i2 - 1]);
            x = max(x, t + f[k - 1][i1][i2 - 1]);           
            x = max(x, t + f[k - 1][i1 - 1][i2]);
            x = max(x, t + f[k - 1][i1][i2]);
        }