动态规划

闫氏DP思考法:从集合角度来考虑DP 问题。

  • image-20220912100452467

  • 状态计算重要的划分依据:依据最后一步来划分集合

  • 集合划分原则:不重复、不遗漏

    • 在求Min/Max, 可以忽略到 不重复这个原则,因为重复对Min和Max的结果不会照成影响
  • 计算顺序:计算时我们必须要保证当前状态需要用到的状态,必须已经被提前计算了。

1、数字三角形模型

这里的状态计算时,因为笔者疏忽,忘记修改状态表示的函数

1015. 摘花生

题目链接

以此题为例,进行闫氏DP分析法,如下。image-20220912101833383

经过上面分析,我们很容易实现如下代码。

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

const int N = 105;
int w[N][N], f[N][N];
int n, m, t;

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

1018. 最低通行费

题目链接

此题我们可以通过 题目说必须 在 2N - 1 事件内走到右下角,所以,也就是表明只能向右或向下走。dp分析如下 image-20220912102935627

注意边界处理:因为必须起点是左上角, 所以需要把左上角的左边或上边一个初始化为0,其他边界全部INF

代码实现如下:

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

const int N = 110, INF = 1e9;
int w[N][N], f[N][N];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            cin >> w[i][j];
            
    // 处理边界问题
    for (int i = 0; i <= n; ++ i) f[0][i] = f[i][0] = INF;
    
    // 因为从进入左上角可以从左边和上边来,所以只需要初始化一个为0即可
    f[0][1] = 0;
    
    for (int i = 1; i <= n; ++ i) 
        for (int j = 1; j <= n; ++ j)
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
    
    cout << f[n][n] << endl;
    return 0;
}

1027. 方格取数

题目链接

这道题是从摘花生题扩展出来的,不过它需要走两次。这个题要求,每个点只能取一次。

思考:

  • 同时走两次,f(i1, j1, i2, j2) 表示 (1, 1)(1, 1) 分别走到 (i1, j1) (i2, j2) 的路径的最大值。
  • 如何处理 “同一个格子不能被重复选择则”
  • 只有在 i1+j1==i2+j2i_1 + j_1 == i_2 + j_2 时,两条路径的格子才有可能重复。
  • 因为两个状态间有关系,可以优化状态表示
  • f(k, i1, i2) 表示 (1, 1)(1, 1) 分别走到 (i1, k - i1) (i2, k - i2) 的路径的最大值。
  • k 表示两条路线走到的格子的横纵坐标和

思维图如下:image-20220912105947689

代码实现如下:

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

const int N = 15, NAV = -1e9;
int f[2 * N][N][N];
int w[N][N];
int n, x, y, num;

int main() {
    cin >> n;
    while(cin >> x >> y >> num, x || y || num)
        w[x][y] = num;
        
    
    for (int k = 2; k <= 2 * 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 <= 0 || j1 > n || j2 <= 0 || j2 > n)
                    continue;
                
                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[2 * n][n][n] << endl;
    return 0;
}


275. 传纸条

题目链接

此题和上一题一模一样,同时走两条路径。

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

const int N = 55;
int f[2 * N][N][N], w[N][N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            cin >> w[i][j];
    
    for (int k = 2; k <= n + m; ++ k) {
        for (int i1 = 1; i1 <= n; ++ i1)
            for (int i2 = 1; i2 <= n; ++ i2) {
                int j1 = k - i1, j2 = k - i2;
                if (j1 <= 0 || j1 > m || j2 <= 0 || j2 > m)
                    continue;
                
                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 + m][n][n] << endl;
    return 0;
}