【动态规划】—— 数字三角形

---

动态规划

动态规划算法把原算法视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算之后，动态规划才会执行下一个阶段的计算。

为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也叫“无后效性”。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。有序无环图中的节点对应问题中的“状态”，图中的边则是对应状态之间的“转移”，转移的选取就是动态规划中的“决策”。

在很多情况下，动态规划用于求解最优化问题。此时，下一阶段的最优解应该能够由前前面各阶段的子问题的最优解求出。这个条件被称为“最优子结构性质”。

“状态”、“阶段”和“决策”是构成动态规划算法的三要素，而“子问题重叠性”，“无后效性”和“最优子结构性”是问题能用动态规划求解的三个基本条件。

动态规划算法把相同的计算过程作用于各阶段的同类子问题，就好像把一个固定的公式套在格式相投的若干输入数据上运行。因此，我们一般只需要定义出DP的计算过程，就可以编程实现了，这个计算过程就称为“状态转移方程”。

闫式思考法

从集合的角度来思考问题： 

---

例题：AcWing 1015. 摘花生

---

集合含义：所有从   走到   的所有路线的最大值 

在状态计算中，很重要的划分依据：“最后”

集合的划分依据：1.不重 2.不漏（在不重复这一点是，可以出现重复算，因为最后是取子集的最最值）

---

AC代码 

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;

int n, m;
int w[N][N];
int f[N][N];

int main()
{
    int T; cin >> T;
    while(T -- )
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ ) 
                scanf("%d", &w[i][j]);
        
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                f[i][j] = max(f[i][j - 1], f[i - 1][j]) + w[i][j];
        cout << f[n][m] << endl;
    }
    return 0;
}

---

例题：AcWing 1018. 最低通行费 

---

跟上面的摘花生的是类似的题目类型。多了时间上面的限制（  ）。

这个时间上面的限制 等价于不走回头路

由于所求的是最小值，这道题在求解的时候需要对边界进行初始化。

---

AC代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n;
int w[N][N];
int f[N][N];


int main()
{
    cin >> n;
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            scanf("%d", &w[i][j]);
    
    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] = INF;
                if(i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
                if(j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
            }
            
    cout << f[n][n] << endl;        
    return 0;
} 

---

例题：AcWing 1027. 方格取数

输入样例：

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出样例：

67

---

这一题相比于前面两题，多了总共走两次这样的限制条件。 

在只走一次的情况中:

 表示的是 所有从   走到   的所有路线的最大值 

走两次的情况中:

 表示所有从 ， 走到  的路径的所有集合的最大值

如何处理“同一个格子不能被重复选择”？

只有在  时，两条路径的格子才会重合 

  表示两个人同时走 k 步（横纵坐标之和）（类比摘花生）

 表示所有从  ，  分别走到  的路径的最大值

---

AC代码 

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N * 2][N][N];

int main()
{
    cin >> n;
    int a, b, c;
    while(cin >> a >> b >> c, a || b || c) w[a][b] = c;
    
    for(int k = 2; k <= n + n; k ++ )
        for(int i1 = 1; i1 <= n; i1 ++ )
            for(int i2 = 1; i2 <= n; i2 ++ )
            {
                int j1 = k - i1, j2 = k - i2;
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = w[i1][j1];
                    if(i1 != i2) t += w[i2][j2];
                    int &x = f[k][i1][i2];
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1 - 1][i2] + t);
                    x = max(x, f[k - 1][i1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1][i2] + t);
                }
            }
    cout << f[n + n][n][n];
    return 0;
}

---