Динамическое программирование на деревьях | Комплект-1

Опубликовано: 17 Января, 2022

Динамическое программирование (DP) - это метод решения проблем путем разбиения их на перекрывающиеся подзадачи в соответствии с оптимальной подструктурой. Существуют различные задачи, использующие DP, такие как сумма подмножества, рюкзак, размена монет и т. Д. DP также может применяться к деревьям для решения некоторых конкретных задач.
Предварительное условие: DFS
Для дерева с N узлами и N-1 ребрами вычислите максимальную сумму значений узлов от корня до любого из листьев без повторного посещения какого-либо узла.

Выше приведена диаграмма дерева с N = 14 узлами и N-1 = 13 ребрами. Значения в узле равны 3, 2, 1, 10, 1, 3, 9, 1, 5, 3, 4, 5, 9 и 8 соответственно для узлов 1, 2, 3, 4… .14.
На схеме ниже показаны все пути от корня до листьев:

Все пути отмечены разными цветами:
Путь 1 (красный, 3-2-1-4): сумма всех значений узлов = 10
Путь 2 (оранжевый, 3-2-1-5): сумма всех значений узлов = 11
Путь 3 (желтый, 3-2-3): сумма всех значений узлов = 8
Путь 4 (зеленый, 3-1-9-9): сумма всех значений узлов = 22
Путь 5 (фиолетовый, 3-1-9-8): сумма значений всех узлов = 21
Путь 6 (розовый, 3-10-1): сумма всех значений узлов = 14
Путь 7 (синий, 3-10-5): сумма всех значений узлов = 18
Путь 8 (коричневый, 3-10-3): сумма всех значений узлов = 16
Ответ - 22, поскольку путь 4 имеет максимальную сумму значений узлов на своем пути от корня до листьев.

Жадный подход в этом случае не срабатывает . Начиная с корня и жадно берите 3 с первого уровня, 10 со следующего уровня и 5 с третьего уровня. Результатом будет путь-7, если после следования жадному подходу, следовательно, здесь не применять жадный подход.
Проблему можно решить с помощью динамического программирования на деревьях. Начните запоминание с листьев и добавьте максимум листьев в корень каждого поддерева. На последнем шаге будет корень и поддерево под ним, добавление значения в узле и максимуме поддерева даст нам максимальную сумму значений узлов от корня до любого из листьев.

На диаграмме выше показано, как начать с листьев и добавить максимальное количество листьев поддерева к его корню . Двигайтесь вверх и повторите ту же процедуру, сохраняя максимум листьев каждого поддерева и добавляя его к его корню. В этом примере для подсчета берется максимум узлов 11 и 12, а затем добавляется к узлу 5 ( в этом поддереве 5 - корень, а 11, 12 - его листья ). Точно так же для подсчета берется максимум узлов 13 и 14, а затем добавляется к узлу 7. Повторите шаги для каждого поддерева, пока мы не дойдем до узла.

Let DPi be the maximum summation of node values in the path between i and any of its leaves moving downwards. Traverse the tree using DFS traversal. Store the maximum of all the leaves of the sub-tree, and add it to the root of the sub-tree. At the end, DP1 will have the maximum sum of the node values from root to any of the leaves without re-visiting any node. 
Below is the implementation of the above idea : 
 

C++

// C++ code to find the maximum path sum
#include <bits/stdc++.h>
using namespace std;
 
int dp[100];
 
// function for dfs traversal and to store the
// maximum value in dp[] for every node till the leaves
void dfs(int a[], vector<int> v[], int u, int parent)
{
    // initially dp[u] is always a[u]
    dp[u] = a[u - 1];
 
    // stores the maximum value from nodes
    int maximum = 0;
 
    // traverse the tree
    for (int child : v[u]) {
 
        // if child is parent, then we continue
        // without recursing further
        if (child == parent)
            continue;
 
        // call dfs for further traversal
        dfs(a, v, child, u);
 
        // store the maximum of previous visited node
        // and present visited node
        maximum = max(maximum, dp[child]);
    }
 
    // add the maximum value returned to the parent node
    dp[u] += maximum;
}
 
// function that returns the maximum value
int maximumValue(int a[], vector<int> v[])
{
    dfs(a, v, 1, 0);
    return dp[1];
}
 
// Driver Code
int main()
{
    // number of nodes
    int n = 14;
 
    // adjacency list
    vector<int> v[n + 1];
 
    // create undirected edges
    // initialize the tree given in the diagram
    v[1].push_back(2), v[2].push_back(1);
    v[1].push_back(3), v[3].push_back(1);
    v[1].push_back(4), v[4].push_back(1);
    v[2].push_back(5), v[5].push_back(2);
    v[2].push_back(6), v[6].push_back(2);
    v[3].push_back(7), v[7].push_back(3);
    v[4].push_back(8), v[8].push_back(4);
    v[4].push_back(9), v[9].push_back(4);
    v[4].push_back(10), v[10].push_back(4);
    v[5].push_back(11), v[11].push_back(5);
    v[5].push_back(12), v[12].push_back(5);
    v[7].push_back(13), v[13].push_back(7);
    v[7].push_back(14), v[14].push_back(7);
 
    // values of node 1, 2, 3....14
    int a[] = { 3, 2, 1, 10, 1, 3, 9, 1, 5, 3, 4, 5, 9, 8 };
 
    // function call
    cout << maximumValue(a, v);
 
    return 0;
}

Java

// Java code to find the maximum path sum
import java.util.Vector;
 
class GFG
{
    static int[] dp = new int[100];
 
    // function for dfs traversal and to
    // store the maximum value in dp[]
    // for every node till the leaves
    static void dfs(int[] a, Vector<Integer>[] v,
                    int u, int parent)
    {
 
        // initially dp[u] is always a[u]
        dp[u] = a[u - 1];
 
        // stores the maximum value from nodes
        int maximum = 0;
 
        // traverse the tree
        for (int child : v[u])
        {
 
            // if child is parent, then we continue
            // without recursing further
            if (child == parent)
                continue;
 
            // call dfs for further traversal
            dfs(a, v, child, u);
 
            // store the maximum of previous visited
            // node and present visited node
            maximum = Math.max(maximum, dp[child]);
        }
 
        // add the maximum value returned
        // to the parent node
        dp[u] += maximum;
    }
 
    // function that returns the maximum value
    static int maximumValue(int[] a,
                            Vector<Integer>[] v)
    {
        dfs(a, v, 1, 0);
        return dp[1];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Driver Code
        int n = 14;
 
        // adjacency list
        @SuppressWarnings("unchecked")
        Vector<Integer>[] v = new Vector[n + 1];
 
        for (int i = 0; i < v.length; i++)
            v[i] = new Vector<>();
 
        // create undirected edges
        // initialize the tree given in the diagram
        v[1].add(2); v[2].add(1);
        v[1].add(3); v[3].add(1);
        v[1].add(4); v[4].add(1);
        v[2].add(5); v[5].add(2);
        v[2].add(6); v[6].add(2);
        v[3].add(7); v[7].add(3);
        v[4].add(8); v[8].add(4);
        v[4].add(9); v[9].add(4);
        v[4].add(10); v[10].add(4);
        v[5].add(11); v[11].add(5);
        v[5].add(12); v[12].add(5);
        v[7].add(13); v[13].add(7);
        v[7].add(14); v[14].add(7);
 
        // values of node 1, 2, 3....14
        int a[] = { 3, 2, 1, 10, 1, 3, 9,
                    1, 5, 3, 4, 5, 9, 8 };
 
        // function call
        System.out.println(maximumValue(a, v));
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 code to find the maximum path sum
dp = [0]*100
 
# Function for dfs traversal and
# to store the maximum value in
# dp[] for every node till the leaves
def dfs(a, v, u, parent):
     
    # Initially dp[u] is always a[u]
    dp[u] = a[u - 1]
     
    # Stores the maximum value from nodes
    maximum = 0
     
    # Traverse the tree
    for child in v[u]:
         
        # If child is parent, then we continue
        # without recursing further
        if child == parent:
            continue
         
        # Call dfs for further traversal
        dfs(a, v, child, u)
         
        # Store the maximum of previous visited 
        # node and present visited node
        maximum = max(maximum, dp[child])
         
    # Add the maximum value
    # returned to the parent node
    dp[u] += maximum
 
 
# Function that returns the maximum value
def maximumValue(a, v):
    dfs(a, v, 1, 0)
    return dp[1]
 
# Driver Code
def main():
     
    # Number of nodes
    n = 14
     
    # Adjacency list as a dictionary
    v = {}
    for i in range(n + 1):
        v[i] = []
         
    # Create undirected edges
    # initialize the tree given in the diagram
    v[1].append(2), v[2].append(1)
    v[1].append(3), v[3].append(1)
    v[1].append(4), v[4].append(1)
    v[2].append(5), v[5].append(2)
    v[2].append(6), v[6].append(2)
    v[3].append(7), v[7].append(3)
    v[4].append(8), v[8].append(4)
    v[4].append(9), v[9].append(4)
    v[4].append(10), v[10].append(4)
    v[5].append(11), v[11].append(5)
    v[5].append(12), v[12].append(5)
    v[7].append(13), v[13].append(7)
    v[7].append(14), v[14].append(7)
     
    # Values of node 1, 2, 3....14
    a = [ 3, 2, 1, 10, 1, 3, 9,
          1, 5, 3, 4, 5, 9, 8 ]
     
    # Function call
    print(maximumValue(a, v))
main()
 
# This code is contributed by stutipathak31jan 

C#

// C# code to find the maximum path sum
using System;
using System.Collections.Generic;
 
class GFG
{
    static int[] dp = new int[100];
 
    // function for dfs traversal and to
    // store the maximum value in []dp
    // for every node till the leaves
    static void dfs(int[] a, List<int>[] v,
                    int u, int parent)
    {
 
        // initially dp[u] is always a[u]
        dp[u] = a[u - 1];
 
        // stores the maximum value from nodes
        int maximum = 0;
 
        // traverse the tree
        foreach(int child in v[u])
        {
 
            // if child is parent, then we continue
            // without recursing further
            if (child == parent)
                continue;
 
            // call dfs for further traversal
            dfs(a, v, child, u);
 
            // store the maximum of previous visited
            // node and present visited node
            maximum = Math.Max(maximum, dp[child]);
        }
 
        // add the maximum value returned
        // to the parent node
        dp[u] += maximum;
    }
 
    // function that returns the maximum value
    static int maximumValue(int[] a,
                            List<int>[] v)
    {
        dfs(a, v, 1, 0);
        return dp[1];
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
 
        // Driver Code
        int n = 14;
 
        // adjacency list
 
        List<int>[] v = new List<int>[n + 1];
 
        for (int i = 0; i < v.Length; i++)
            v[i] = new List<int>();
 
        // create undirected edges
        // initialize the tree given in the diagram
        v[1].Add(2); v[2].Add(1);
        v[1].Add(3); v[3].Add(1);
        v[1].Add(4); v[4].Add(1);
        v[2].Add(5); v[5].Add(2);
        v[2].Add(6); v[6].Add(2);
        v[3].Add(7); v[7].Add(3);
        v[4].Add(8); v[8].Add(4);
        v[4].Add(9); v[9].Add(4);
        v[4].Add(10); v[10].Add(4);
        v[5].Add(11); v[11].Add(5);
        v[5].Add(12); v[12].Add(5);
        v[7].Add(13); v[13].Add(7);
        v[7].Add(14); v[14].Add(7);
 
        // values of node 1, 2, 3....14
        int []a = { 3, 2, 1, 10, 1, 3, 9,
                    1, 5, 3, 4, 5, 9, 8 };
 
        // function call
        Console.WriteLine(maximumValue(a, v));
    }
Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022