01背包问题

题目来源:

2. 01背包问题 - AcWing题库

具体代码:

没有优化前：状态方程是二维的时候

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;//n个物品，最大容量为m
int v[N],w[N];//每个物品的体积Vi和价值Wi
int f[N][N];//状态转移方程
int main(void){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout << f[n][m]<<endl;
    
    return 0;
}

利用滚动数组优化为一维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

对目前的我来说只是简单理解，但是化成文字还是有点困难。等我完全理解了再做解析

其他参考博客：

dd大牛的《背包九讲》 - 贺佐安 - 博客园 (cnblogs.com) （需要仔细研读）

(56条消息) 动态规划专题——背包问题_动态规划 背包_Iareges的博客-CSDN博客

AcWing 2. 01背包问题 - AcWing

完全背包问题

状态转移方程

1
f[i,j]=max(f[i][j],f[i-1,j-v[i]*k]+w[i]*k);

优化：

1
2
f[i][j]   =    Max(f[i-1][j],f[i-1,j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w...)              (1)
f[i][j-v]=    Max(            f[i-1][j-v],   f[i-1][j-2v]+w,  f[i-1][j-3v]+2w...)              (2)

对比(1)(2)可知，（1）中f[i-1,j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w...为(2)f[i][j-v]+w即可

即: 优化后的完全背包为

f[i][j]=Max(f[i-1][j],f[i][j-v]+w)

完整代码如下:

1
2
3
4
5
6
7
for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        f[i][j]=f[i-1][j];
        if(j>=v[i])f[i][j]=Max(f[i-1][j],f[i][j-v[i]]+w[i]);
    }
}
cout<<f[n][m];

对比完全背包和01背包状态转移方程可知

1
2
3
4
//01背包
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
//完全背包
f[i][j]=Max(f[i-1][j],f[i][j-v[i]]+w[i]);

只有一个地方不同，就是01背包是f[i-1][j-v[i]]而完全背包是f[i][j-v[i]]一个是从i-1的状态转移而来，另外一个是从i个状态转移而来，原因还是因为，完全背包可以重复选取！

完全背包也可以优化为1维:

1
2
3
4
5
6
for(int i=1;i<=n;i++){
    for(int j=v[i];j<=m;j++){
        f[j]=Max(f[j],f[j-v[i]]+w[i]);
    }
}
cout<<f[m];

注意这里对j不需要倒序，因为我们的f[j-v[i]]与f[j]是都在i层，而且需要从前往后推导的

多重背包问题

每件物品的个数有限制，有s[i]件

动态规划:

  1. 状态表示f[i][j]:

    1. 集合：所有只从前i个物品中选，并且总体积不超过j的选法
    2. 属性:Max

  2. 状态计算

    1. 最朴素的三重循环

      1
      2
      3
      4
      5
      6
      7
      for(int i=1;i<=n;i++){
          for(int j=0;j<=m;j++){
              for(int k=0;k<=s[i]&&k*v[i]<=j;k++)// k是物品的个数
                  f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k)
          }
      }
      cout<<f[n][m]<<endl;

    2. 优化算法:（错）

      如果我们尝试使用完全背包的优化方法：

      1
      2
      f[i][j]     =max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...f[i-1][j-sv]+sw)  （1）
      f[i][j-v]  =max(            f[i-1][j-v]      ,f[i-1][j-2v]+w,...f[i-1][j-sv]+(s-1)w+f[i-1][j-v-sv]+sw)(2)

      第二项最后的f[i-1][j-v-sv]+sw怎么来的呢？

      引用网上一个讲解

      • 体积j，考虑第i个物品时，我们会考虑放0个，1个，2个，3个，….，一直到放不下第i个物品 或者物品不够用为止 为止（这里物品不够用就是关键了，比如我们的体积j非常大，第i个物品只有3个，那么最后一项就是 f(i - 1, j - 3*vi) + 3 * wi
      • 对于体积 j - vi，考虑第i个物品时，第i个物品只有3个，假设j - vi的体积也都能放下它们，那么最后一项就是 f(i - 1, j - vi - 3*vi) + 3 * wi

      1. 正确的优化算法

        二进制优化：不懂就去看y总视频讲解，这个太牛逼了

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        #include <iostream>
        #include <algorithm>

        using namespace std;

        const int N = 12010, M = 2010;

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

        int main()
        {
            cin >> n >> m;

            int cnt = 0;
            for (int i = 1; i <= n; i ++ )
            {
                int a, b, s;
                cin >> a >> b >> s;
                int k = 1;
                while (k <= s)
                {
                    cnt ++ ;
                    v[cnt] = a * k;
                    w[cnt] = b * k;
                    s -= k;
                    k *= 2;
                }
                if (s > 0)
                {
                    cnt ++ ;
                    v[cnt] = a * s;
                    w[cnt] = b * s;
                }
            }

            n = cnt;

            for (int i = 1; i <= n; i ++ )
                for (int j = m; j >= v[i]; j -- )
                    f[j] = max(f[j], f[j - v[i]] + w[i]);

            cout << f[m] << endl;

            return 0;
        }

分组背包问题

9. 分组背包问题 - AcWing题库

分组背包问题：

有 N组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 V[i][j]，价值是 w[i][j]，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

  1. 状态表示f[i][j]

    1. 集合：从前i个物品中选，且总体积不大于j的所有选法
    2. 属性：Max

  2. 状态计算

    状态转移方程:

    1
    f[i-1][j]=Max(f[i-1][j],f[i-1][j-v[i,k]]+w[i,k]);

    对每一组中物品的选择，由于每一组中物品的价值和重量也不一样，所以可以认为是每一组的01背包问题

    代码如下：

    二维：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    #include<bits/stdc++.h>
    using namespace std;

    const int N=110;
    int f[N][N];  //只从前i组物品中选，当前体积小于等于j的最大值
    int v[N][N],w[N][N],s[N];   //v为体积，w为价值，s代表第i组物品的个数
    int n,m,k;

    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>s[i];
            for(int j=0;j<s[i];j++){
                cin>>v[i][j]>>w[i][j];  //读入
            }
        }

        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                f[i][j]=f[i-1][j];  //不选
                for(int k=0;k<s[i];k++){
                    if(j>=v[i][k])     f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);  
                }
            }
        }
        cout<<f[n][m]<<endl;
    }

    一维：由于我们认为是每一组是01背包问题，所以体积从大到小，至于每一组的时候为什么先循环体积再循环物品个数，原因如下：

    还是滚动数组的问题，在二维循环中是可以这么来做的，但是在压缩数组以后：

    如果优化了第一维坐标只用f[j]的话 正常顺序先遍历j再枚举物品时 只会修改当前这个j 意思是枚举物品这一层循环不会互相影响 但是如果先枚举物品k = k1时进入j循环 修改了f[j-v[i][k1] 然后枚举下一个物品k = k2时 用到的f[j-v[i][k2]]可能跟f[j-v[i][k1]]相等，也就是被k1修改过了 而分组背包每一组最多选一个，理论上是不会互相影响的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <iostream>
    #include <algorithm>

    using namespace std;

    const int N = 110;

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

    int main()
    {
        cin >> n >> m;

        for (int i = 1; i <= n; i ++ )
        {
            cin >> s[i];
            for (int j = 0; j < s[i]; j ++ )
                cin >> v[i][j] >> w[i][j];
        }

        for (int i = 1; i <= n; i ++ )
            for (int j = m; j >= 0; j -- )
                for (int k = 0; k < s[i]; k ++ )
                    if (v[i][k] <= j)
                        f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

        cout << f[m] << endl;

        return 0;
    }

线性DP

数字三角形

898. 数字三角形 - AcWing题库

针对这个题展开线性DP记录

状态表示

  1. 集合：所有从起点走到i,j的路径
  2. 属性：Max

状态计算

对于i,j,比较来自左上方和上方的两个值

1
f[i][j]=Max(f[i-1][j-1],f[i-1][j])+a[i][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include<iostream>
#include<algorithm>
using namespace std;
const int INF=1e9;
const int N =510;
int n;
int dp[N][N];
int a[N][N];
int main(void){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i+1;j++){
            dp[i][j]=-INF;
        }
    }
    dp[1][1]=a[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
        }
    }
    int Maxnum=-INF;
    for(int j=1;j<=n;j++){
        Maxnum=max(Maxnum,dp[n][j]);
    }
    cout<<Maxnum;

    return 0;
}

注意数组的初始化大小以及初始化的i,j的值！！

最长上升子序列

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

状态表示

集合：所有以i结尾的上升子序列的最大值

属性:Max

状态计算

1
f[i]=max(f[j]+1) j=1=0,1,2,3,4..i-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
int n;
int dp[N];
int a[N];
int main(void){
    
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<=i-1;j++){
            if(a[j]<a[i])
            dp[i]=max(dp[i],dp[j]+1);
        }
    }
    int Maxnum=0;
    for(int i=1;i<=n;i++){
        Maxnum=max(dp[i],Maxnum);
    }
    cout<<Maxnum;
    return 0;
}

最长公共子序列

897. 最长公共子序列 - AcWing题库

状态表示

集合：f[i][j]

所有由第一个序列前i个字母中出现和第二个序列的前j个字母中出现的子序列公共子序列

属性：Max

状态计算

image-20230606101543425

以a[i]和b[j]是否包含在子序列当中来作为划分依据

f[i][j]=max(f[i-1][j-1],f[i-1][j],f[i][j-1],f[i-1][j-1]+1)

但是需要说明的是

f[i-1][j]和f[i][j-1]表示的不是01和10这两种情况

01情况：即a序列不包含i和b的子序列包含j的最长子序列

而f[i-1][j]的值是前a中前i-1个序列和b中前j个序列的最长子序列

如果把f[i-1][j]用上面的图表示，其中f[i-1][j]中11的情况才是满足的f[i][j]中01的情况的

所以f[i-1][j]>=f[i][j]的01情况的，但是我们仍然可以用f[i-1][j]来代替01的情况，因为属性是最大值，可以允许有交集

给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
int n,m;
char a[N],b[N];
int dp[N][N];
int main(void){
    
    cin>>n>>m;
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    cout<<dp[n][m];
    
    return 0;
}

区间dp问题

282. 石子合并 - AcWing题库

在一个区间内的进行DP问题

状态表示

f[i][j]表示i到j的一个区间

集合：所有将第i堆石子到第j堆石子合并为一堆石子的合并方式

属性：合并方式的代价最小值 Min

状态计算

这是一种错误的做法：不可以枚举端点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<algorithm>
using namespace std;
const int N =310,INF=1e9;
int n;
int dp[N][N];
int a[N],s[N];
int main(void){
    
    cin>>n;
     for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=INF;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];// 前缀和
        dp[i][i]=a[i];
    }
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            dp[i][j]=s[j]-s[i-1];
        }
    }
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=i;k<j;k++){
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<dp[1][n];
    
    return 0;
}

正确方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);

    for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];

    for (int len = 2; len <= n; len ++ )
        for (int i = 1; i + len - 1 <= n; i ++ )
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for (int k = l; k < r; k ++ )
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }

    printf("%d\n", f[1][n]);
    return 0;
}

数位dp

338. 计数问题 - AcWing题库

image-20230609152835801

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
/*

/*/

int get(vector<int> num,int l,int r)//因为我们举的分类中，有需要求出一串数字中某个区间的数字，例如abcdefg有一个分类需要求出efg+1
{
    int res=0;
    for(int i=l;i>=r;i--) res=res*10+num[i];//这里从小到大枚举是因为下面count的时候读入数据是从最低位读到最高位，那么此时在num里，最高位存的就是数字的最低位，那么假如我们要求efg，那就是从2算到0
    return res;
}

int power10(int i)//这里有power10是因为有一个分类需要求得十次方的值，例如abc*10^3
{
    int res=1;
    while(i--) res*=10;
    return res;
}

int count(int n,int x)
{
    vector<int> num;//num用来存储数中每一位的数字
    while(n)
    {
        num.push_back(n%10);//get里有解释
        n/=10;
    }
    n=num.size();//得出他的长度
    int res=0;
    for(int i=n-1-!x;i>=0;i--)//这里需要注意，我们的长度需要减一，是因为num是从0开始存储，而长度是元素的个数，因此需要减1才能读到正确的数值，而！x出现的原因是因为我们不能让前导零出现，如果此时需要我们列举的是0出现的次数，那么我们自然不能让他出现在第一位，而是从第二位开始枚举
    {
        if(i<n-1)//其实这里可以不用if判断，因为for里面实际上就已经达成了if的判断，但为了方便理解还是加上if来理解，这里i要小于n-1的原因是因为我们不能越界只有7位数就最高从七位数开始读起
        {
            res+=get(num,n-1,i+1)*power10(i);//这里就是第一个分类，000~abc-1,那么此时情况个数就会是abc*10^3，这里的3取决于后面efg的长度，假如他是efgh，那么就是4
            //这里的n-1，i-1，自己将数组列出来然后根据分类标准就可以得出为什么l是n-1，r是i-1
            if(!x) res-=power10(i);//假如此时我们要列举的是0出现的次数，因为不能出现前导零，这样是不合法也不符合我们的分类情况，例如abcdefg我们列举d，那么他就得从001~abc-1，这样就不会直接到efg，而是会到0efg，因为前面不是前导零，自然就可以列举这个时候0出现的次数，所以要减掉1个power10
        }
        //剩下的这两个就直接根据分类标准来就好了
        if(num[i]==x) res+=get(num,i-1,0)+1;
        else if(num[i]>x) res+=power10(i);
    }
     return res;//返回res，即出现次数
}

int main()
{
    int a,b;
    while(cin>>a>>b,a)//读入数据，无论a，b谁是0，都是终止输入，因为不会有数字从零开始（a，b>0）
    {
        if(a>b) swap(a,b);//因为我们需要从小到大，因此如果a大于b，那么就得交换，使得a小于b
        for(int i=0;i<=9;i++)//列举a和b之间的所有数字中 0∼9的出现次数
        cout<<count(b,i)-count(a-1,i)<<' ';//这里有点类似前缀和，要求a和b之间，那么就先求0到a i出现的次数，再求0到b i出现的次数，最后再相减就可以得出a和b之间i出现的次数
        cout<<endl;
    }
    return 0;
}

状态压缩dp

91. 最短Hamilton路径 - AcWing题库

AcWing 91. 最短Hamilton路径(超详解) - AcWing

AcWing 91. 最短Hamilton路径（管家级详解） - AcWing

这真是个好题！！！

状态表示：

集合：f[i,j]：集合：所有从0号走到j号，走过的所有点是i的所有路径

属性：Min

状态计算：

根据倒数第二个点来求，就是从0走到j倒数第二个点是0…j-1的所有走法

image-20230609155935431

假如是从 0—k—-j 从0经过k到j一共走了i个点，

k到j的长度已经确定了。0—k走过i-1个点的长度应该是

f(i-{j},k)+a(k,j);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=20,M=1<<N;
int f[M][N],weight[N][N];

int main(void){
    
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>weight[i][j];
        }
    }
    memset(f,0x3f,sizeof(f));//因为是要求最小值，所以初始化最大值
    f[1][0]=0;
    for(int i=0;i<1<<n;i++){ // 遍历每个状态 从 000000... 到 111111... (1<<n) 是1000000 有七个  
        for(int j=0;j<n;j++){ // 遍历以j结尾的终点
            if(i>>j&1){  // i 右边移动j位 和1 &运算，可以判断是否第j位是1，也就是判断第j位是否走过
                for(int k=0;k<n;k++){
                    if(i>>k&1){ // k是j倒数第二个点，来遍历j  [...k,j...]
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+weight[k][j]); // 把第j位给剪掉，保证k是在j结点之前最后一个结点
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1]<<endl; // 最后的这个1<<n-1  就是保证所有点都走过了，就是 0到n-1 的结点，是1111_1111有n-1个1
    
    return 0;
}

树形dp

状态表示：

集合：f[u][0]：所有以U为根的子树中选并且不选u这个点的方案

​ f[u][1]：所有以u为根的子树中选，并且选u这个点的方案

属性：Max

对于 u 的子节点 s0 s1 等

f(u,0)=max(f(s0,0),f(s1,1))+max(f(s0,0),f(s1,1))+…max(f(si,0),f(si,1)) i取遍每个子节点[子节点选上和不选都可以]

f(u,1)=f(s0,0)+f(s1,0)+…f(si,0) i取遍每个子节点 选了根节点，就不可以选子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int n;
int happy[N]; //每个职工的高兴度
int f[N][2]; //上面有解释哦~
int e[N],ne[N],h[N],idx; //链表，用来模拟建一个树
bool has_father[N]; //判断当前节点是否有父节点
void add(int a,int b){ //把a插入树中
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void dfs(int u){ //开始求解题目
    f[u][1] = happy[u]; //如果选当前节点u，就可以把f[u,1]先怼上他的高兴度
    for(int i = h[u];~i;i = ne[i]){ //遍历树
        int j = e[i];
        dfs(j); //回溯
        //状态转移部分，上面有详细讲解~
        f[u][0] += max(f[j][1],f[j][0]);
        f[u][1] += f[j][0];
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&happy[i]); //输入每个人的高兴度
    memset(h,-1,sizeof h); //把h都赋值为-1
    for(int i = 1;i < n;i ++){
        int a,b; //对应题目中的L,K,表示b是a的上司
        scanf("%d%d",&a,&b); //输入~
        has_father[a] = true; //说明a他有爸爸（划掉）上司
        add(b,a); //把a加入到b的后面
    }
    int root = 1; //用来找根节点
    while(has_father[root]) root ++; //找根节点
    dfs(root); //从根节点开始搜索
    printf("%d\n",max(f[root][0],f[root][1])); //输出不选根节点与选根节点的最大值
    return 0;
}

如何用邻接表来表示树

重点是三个数组 h, e ,ne

h[k]存储这个单链表的头结点，e[]存储数据域的值，ne[]存储结点的next指针

初始化

1
2
idx = 0;
memeset(h, -1, sizeof(h));
1
2
3
void add(int a,int b){ //添加一条边a->b
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

记忆化搜索

901. 滑雪 - AcWing题库

AcWing 901. 滑雪 - AcWing

状态表示：所有从i,j开始滑的路径

属性：所有路劲的最大长度 MAX

状态计算：

分类讨论，上下左右四个方向滑雪

f[i][j]=f[i][j+1]+1

f记忆化搜索表示的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N =400;
int h[N][N];
int f[N][N];
int MaxLenth;
int n,m;
int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1}; // 下上左右遍历
int dp(int x,int y){
    int &F=f[x][y];
    if(F!=-1) return F;
    F=1;//状态先赋值为1
    for(int i=0;i<4;i++){
       int a=x+dx[i],b=y+dy[i];
       if(a>=1 && a<=n && b>=1 && b<=m && h[a][b]<h[x][y]){
           F=max(F,dp(a,b)+1);
       }
    }
    return F;
}

int main(void){

   cin>>n>>m;
   for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
           cin>>h[i][j];
       }
   }
   memset(f,-1,sizeof(f));
   for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
           MaxLenth=max(MaxLenth,dp(i,j));   
       }
   }
   
  cout<<MaxLenth;
       
    return 0;
}

树形dp 打家劫舍

树形DP：

337. 打家劫舍 III - 力扣（LeetCode）

  • 状态定义

f[u][0]：以节点u为根节点且不选根节点的子树的最大金额；

f[u][1]：以节点u为根节点且选根节点的子树的最大金额；

  • 状态转移方程

f[u][0]=max(f[s1][0], f[s1][1]) + max(f[s2][0], f[s2][1]);

f[u][1]=u.val + f[s1][0] + f[s2][0];

其中，s1和s2表示节点u的两个子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    typedef pair<int,int>PII;
    PII dfs(TreeNode*root){
        if(root==NULL) return {0,0};
        auto left=dfs(root->left);
        auto right=dfs(root->right);
        int res0 = max(left.first,left.second)+max(right.first,right.second);
        int res1 = root->val+left.first+right.first;
        return {res0,res1};//选与不选
    }
    int rob(TreeNode* root) {
       auto res=dfs(root);
       return max(res.first,res.second);
    }
};