[数据结构与算法]第一章：动态规划

1.1 数字三角形模型

集合角度考虑DP问题

数字三角形

摘花生

#include<bits/stdc++.h>

using namespace std;
const int N = 110;

int w[N][N];
int dp[N][N];

int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        memset(w, 0, sizeof w);
        memset(dp, 0, sizeof dp);
        int r, c;
        cin >> r >> c;
        for (int i = 1; i <= r; i ++)
        {
            for (int j = 1; j <= c;j ++)
            {
                int m;
                cin >> m;
                w[i][j] = m;
            }
        }
        for (int i = 1; i <= r; i ++)
        {
            for (int j = 1; j <= c; j ++)
            {
                dp[i][j] = max(dp[i - 1][j] + w[i][j], dp[i][j - 1] + w[i][j]);
            }
        }
        cout << dp[r][c] << endl;
    }
}

最低通行费

#include<bits/stdc++.h>

using namespace std;
const int N = 110;
int w[N][N];
int f[N][N];
int main()
{
    int n;
    cin >> n;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
        {
            cin >> w[i][j];
        }
    }
    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] = min(f[i][j], f[i][j - 1] + w[i][j]);//这里取的是三者的最小值
        }
    }
    cout << f[n][n] << endl;
}

方格取数
题解

#include<bits/stdc++.h>

using namespace std;
const int N = 15;
int w[N][N];
int f[2 * N][N][N];
int main()
{
    int n;
    cin >> n;
    int a, b, c;
    while (cin >> a >> b >> c && (a || b || c))
    {
        w[a][b] = c;
    }
    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 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int &x = f[k][i1][i2], t = w[i1][j1];
                    if (i1 != i2) t += w[i2][j2];
                    x = max(x, f[k-1][i1-1][i2-1] + t);
                    x = max(x, f[k-1][i1][i2-1] + t);
                    x = max(x, f[k-1][i1-1][i2] + t);
                    x = max(x, f[k-1][i1][i2] + t);
                }
            }
        }
    }
    
    cout << f[2 * n][n][n];
}