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

作者：从前慢现在也慢 | 2024-04-25 23:36:13

踩

【动规】数字三角形

动态规划

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

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

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

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

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

闫式思考法

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

例题：AcWing 1015. 摘花生

集合含义：所有从 $\small (1,1)$ 走到 $\small (i,j)$ 的所有路线的最大值

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

集合的划分依据：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. 最低通行费

跟上面的摘花生的是类似的题目类型。多了时间上面的限制（ $\small \leqslant 2n-1$ ）。

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

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

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. 方格取数

输入样例：

输出样例：

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

在只走一次的情况中:

$\small f[i,j]$ 表示的是所有从 $\small (1,1)$ 走到 $\small (i,j)$ 的所有路线的最大值

$\small f[i,j]=max(f[i - 1][j],f[i][j-1]) +w[i][j]$

走两次的情况中:

$\small f[i_1,i_2,j_1,j_2]$ 表示所有从 $\small (1,1)$ ， $\small (1,1)$ 走到 $\small (i_1,j_1),(i_2,j_2)$ 的路径的所有集合的最大值

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

只有在 $\large {\color{Blue} i_1+j_1=i_2+j_2}$ 时，两条路径的格子才会重合

$\small k=i_1+j_1=i_2+j_2$ 表示两个人同时走 k 步（横纵坐标之和）（类比摘花生）

$\small f[k,i_1,i_2]$ 表示所有从 $\small (1,1)$ ， $\small (1,1)$ 分别走到 $\small (i_1,k-i_1),(i_2,k-i_2)$ 的路径的最大值

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;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/487782