标签：i1 i2 j1 j2 int 动态 规划 AcWing

dp

 

 数字三角形

例题1：

AcWing 1015. 摘花生 - AcWing

题意：

从（1，1）到（r，c）摘花生，不可走回头路，最多可以摘多少

思路：

f[i, j]：（1，1）到（i，j）的最大摘花生数

核心代码：

        for(int i = 1; i <= r; i++)
        {
            for(int j = 1; j <= c; j++)
            {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
            }
        }

        cout << f[r][c] <<'\n';

例题2

1027. 方格取数 - AcWing题库

题意：

从（1，1）到（n，n）在每一个方格中取数，方格中数被取后数变成0，可走两次，问可取最大数为几

思路：

用两次dp无法确定是否是最优解

用f[i1][j1][i2][j2]表示从（1，1）开始同时走分别走到（i1，j1）（i2，j2）的最大取数

i1+j1=i2+j2时才是同时走的

设k = i1+j1

用三维dp，f[k][i1][i2]求解（横纵坐标和为k时，纵坐标走的i1，i2的时候，最大取数）

核心代码：

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

    printf("%d\n", f[n + n][n][n]);

最长上升子序列（LIS）

例题1

895. 最长上升子序列 - AcWing题库

f[i] :所有以a[i]结尾的单调上升子序列长度最大值

核心代码：

    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
        {
            if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
        }
    }

    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        ans = max(ans, f[i]);
    }

    printf("%d", ans);

 

标签：i1,i2,j1,j2,int,动态,规划,AcWing
From： https://www.cnblogs.com/lys-blogs123/p/17204676.html