动态规划之加分二叉树

发表于 | 分类于 | | 阅读次数:

动态规划是我们最常用的算法之一，在我看来动态规划就是利用额外内存空间将运算过程中所需要的重复变量进行记录，下次访问使用的时候直接进行读取从而减少了额外的重复计算，提高了算法的效率，从某种角度来说也算是空间换取时间的一种方式。道理很简单，动态规划的核心是我们对问题的分割和思考，如何构建状态转移方程、分割事件，如何分解一整个问题，这才是动态规划最核心的解决问题的核心思想。
树归即树形动态规划，是在树形结构中使用动态规划的一类问题。因为树形结构没有环，进行深度优先遍历搜索的时候不会重复进行，再加上树形结构本身有着良好的性质和特点，树归的问题非常多，思路也特别有意思。下面将对我在学习过程中遇到的树归问题进行介绍和记录。

加分二叉树

题目要求

【问题描述】
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。
每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都
有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
【输入格式】
第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
【输出格式】
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
【输入样例】

5
5 7 1 2 10

【输出样例】

145
3 1 2 4 5

解题思路

首先分析题目，最直观的解决方法是对问题进行遍历求解，设置起始点i(1=<i<=n)、末结点j(1=<j<=n)和根节点k(i=<k<=j)，依次进行遍历求解，但是这种方法时间复杂度非常高达到了O(n^3)，同时我们发现在(i, k, j)分别取(1, 5, 9)和(2, 5, 9)的时候，由于两种情况下都包含了(k==5 && j==9)这种情况，从而进行了不必要的重复运算，这时候就可以考虑使用动态规划来存储重复计算的结构变量，从而对问题解法进行优化。
这里我们设置dp[i][j]用来表示从第i个结点到第j个结点的最大分数值，建立dp数组将其存储下来，就可以在之后的遍历过程中直接访问使用了，从而大大提高了运算的效率。由此我们也可以得到状态转移方程为：

1
2
3
4
5
6
7
8
dp[i][j] = max
{
    dp[i][i] + dp[i+1][j],                   //第i结点作根结点
    dp[i+1][i+1] + dp[i][i] * dp[i+2][j],    //第i+1结点作根结点
    dp[i+2][i+2] + dp[i][i+1] * dp[i+3][j],  //第i+2结点作根结点
    ...
    dp[i][j-1] + dp[j][j];                   //第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
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
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
using namespace std;
int score[100];//存储每个结点分数
int root[100][100];//存储根结点
int dp[100][100];//存储加分结果
int n;//结点数

void DP()
{
    //只有一个结点加分树结构
    for(int i = 1; i <= n; ++i)
    {
        dp[i][i] = score[i];
        root[i][i] = i;
    }
    //两个结点的加分树结构情况
    for(int i = 1; i < n; ++i)
    {
        dp[i][i+1] = score[i] + score[i+1];
        root[i][i+1] = i;
    }
    //遍历区间为d的两个结点之间的最大分数
    for(int d = 2; d < n; ++d)
    {
        for(int i = 1; i <= n-d; ++i)
        {
            int temp;
            dp[i][i+d] = dp[i][i] + dp[i+1][i+d];
            root[i][i+d] = i;
            for(int j = i+1; j < i+d; ++j)
            {
                temp = dp[i][j-1] * dp[j+1][i+d] + dp[j][j];
                if(temp > dp[i][i+d])
                {
                    dp[i][i+d] = temp;
                    root[i][i+d] = j;
                }
            }
            if(dp[i][i+d-1] + dp[i+d][i+d] > temp)
            {
                dp[i][i+d] = dp[i][i+d-1] + dp[i+d][i+d];
                root[i][i+d] = i+d;
            }
        }
    }
}
//前序遍历函数
void preOrder(int x, int y)
{
    if(x <= y)
    {
        cout << root[x][y] << " ";
        preOrder(x, root[x][y] - 1);
        preOrder(root[x][y] +1, y);
    }
}


int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> score[i];
    }
    DP();
    cout << dp[1][n] << endl;
    preOrder(1, n);
    cout << endl;
    return 0;
}
-------------本文结束感谢您的阅读-------------
0%