## 数字三角形 【干货、背诵版】

#### 基础题

**[$AcWing$ $1015$. 摘花生](https://www.acwing.com/problem/content/1017/)**

二维状态表示，双重循环填充二维表，从上或左可以转移
```cpp {.line-numbers}
  for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                // 递推的出发点，采用特判的办法手动维护，其它的靠关系式递推完成
                // 之所以这样对起点进行初始化，是因为只有这样才能保障逻辑自洽
                if (i == 1 && j == 1)
                    f[i][j] = w[i][j];
                else
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];

```
**初始化**
```cpp {.line-numbers}
 f[1][1] = w[1][1]; //出发点
```
**状态表示**
$f[i][j]$:走到第$(i,j)$个位置时可以获取到的最大数量和

**状态转移**
$f[i][j]$可以从哪些状态转移而来,答：从上方或左方过来

**初始值**
思考起点状态表示的现实含义

**总结**
①  动态规划需要按上面的三步走，而最难的是状态表示，状态转移还好，根据题意推出相应的转换关系。状态表示靠 **经验**，对，是 **经验**。

② 初始值：放在循环内初始化更直接

③ 一维状态表示，我理解不如二维直观，最起码思路应该是先有两维再缩成一维，而不是上来就直接一维。一般的题目不会对内存有严格的限制，能用二维还是二维吧，实在卡内存再考虑降为一维。

**[$AcWing$ $1018$. 最低通行费](https://www.acwing.com/problem/content/1020/)**
与上一题基本一样，只不过是变换了下，需要你用思维转换一下：$2n-1$次，就是说只能向下或向右，否则次数就不达标了。还有一点，求最小值，而不是最大值，其它的没区别
```cpp {.line-numbers}
//初始化为最大值
memset(f, 0x3f, sizeof f);

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        if (i == 1 && j == 1)
            f[i][j] = w[i][j]; //特事特办，不用追求完美的一体化表现，合理特判，逻辑简单
        else
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
    }
```

#### 进阶题

**[$AcWing$ $1027$. 方格取数](https://www.acwing.com/problem/content/1029/)**
走两次，其实是故意让我们真的走两回，每次取最优。

很明显，这是坑。因为如果每次走时不考虑别人，只考虑自己，就是局部最优，不是全局最优，这样就是贪心，不是动态规划。

解决办法就是把两次一起考虑，转化为有两个小人一起走，步调一致，此时两个相亲相爱，互相照顾，白头偕老，皆大欢喜：

状态表示也就呼之欲出：

**状态表示**
① 两个坐标共同决定了现在的状态，换句话说，状态和上面的两个坐标都是相关的
② 当你发现一维不足以表示当前状态时，考虑扩二维，二维不行再考虑扩三维，以此类推。

$f[x_1][y_1][x_2][y_2]$表示第1个人走到$(x_1,y_1)$,第2个人走到$(x_2,y_2)$,但需要保证$x_1+y_1=x_2+y_2$


**状态转移**：
① 如果两个人走到同一个位置，就可能加上一次这个位置上的数
② 如果两个人走到不同的位置，就可以加上两个地方上的数


```cpp {.line-numbers}
 //开始递推
for (int x1 = 1; x1 <= n; x1++)
    for (int y1 = 1; y1 <= n; y1++)
        for (int x2 = 1; x2 <= n; x2++)
            for (int y2 = 1; y2 <= n; y2++) {
                if (x1 + y1 == x2 + y2) {
                    int t = f[x1 - 1][y1][x2 - 1][y2];     //下下
                    t = max(t, f[x1][y1 - 1][x2][y2 - 1]); //右右
                    t = max(t, f[x1 - 1][y1][x2][y2 - 1]); //下右
                    t = max(t, f[x1][y1 - 1][x2 - 1][y2]); //右下
                    //加上这个点的数值
                    f[x1][y1][x2][y2] = t + w[x1][y1];
                    //如果这个点没有被重复走，那么再加一次w(x2,y2)
                    if (x1 != x2 && y1 != y2) f[x1][y1][x2][y2] += w[x2][y2];
                }
            }
```


**[$AcWing$ $275$. 传纸条](https://www.acwing.com/problem/content/277/)**
与上面的题目是一个题。