La programación dinámica (DP) es una técnica para resolver problemas dividiéndolos en subproblemas superpuestos que siguen la subestructura óptima. Hay varios problemas que usan DP como suma de subconjunto, mochila, cambio de moneda, etc. DP también se puede aplicar en árboles para resolver algunos problemas específicos.
Requisito previo: DFS
Dado un árbol con N Nodes y N-1 aristas, calcule la suma máxima de los valores de los Nodes desde la raíz hasta cualquiera de las hojas sin volver a visitar ningún Node.
Lo anterior es un diagrama de un árbol con N=14 Nodes y N-1=13 aristas. Los valores en el Node son 3, 2, 1, 10, 1, 3, 9, 1, 5, 3, 4, 5, 9 y 8 respectivamente para los Nodes 1, 2, 3, 4….14.
El siguiente diagrama muestra todos los caminos desde la raíz hasta las hojas:
Todas las rutas están marcadas con diferentes colores:
Ruta 1 (rojo, 3-2-1-4): suma de todos los valores de Node = 10
Ruta 2 (naranja, 3-2-1-5): suma de todos los valores de Node = 11
Ruta 3 (amarillo, 3-2-3): suma de todos los valores de Node = 8
Ruta 4 (verde, 3-1-9-9): suma de todos los valores de Node = 22
Ruta 5 (violeta, 3-1- 9-8): suma de todos los valores de los Nodes = 21
Ruta 6 (rosa, 3-10-1): suma de todos los valores de los Nodes = 14
Ruta 7 (azul, 3-10-5): suma de todos los valores de los Nodes = 18
Camino 8 (marrón, 3-10-3): suma de todos los valores de los Nodes = 16
La respuesta es 22, ya que el Camino 4 tiene la suma máxima de valores de los Nodes en su camino desde la raíz hasta las hojas.
El enfoque codicioso falla en este caso . Comenzando desde la raíz y tomando 3 del primer nivel, 10 del siguiente nivel y 5 del tercer nivel con avidez. El resultado es la ruta 7 si después de seguir el enfoque codicioso, por lo tanto, no aplique el enfoque codicioso aquí.
El problema se puede resolver usando Programación Dinámica en árboles. Comience a memorizar desde las hojas y agregue el máximo de hojas a la raíz de cada subárbol. En el último paso, habrá raíz y el subárbol debajo de él, agregar el valor en el Node y el máximo del subárbol nos dará la suma máxima de los valores del Node desde la raíz hasta cualquiera de las hojas.
El diagrama anterior muestra cómo comenzar con las hojas y agregar el máximo de hojas de un subárbol a su raíz . Muévase hacia arriba y repita el mismo procedimiento de almacenar el máximo de hojas de cada subárbol y agregarlo a su raíz. En este ejemplo, se toma en cuenta el máximo de los Nodes 11 y 12 y luego se suma al Node 5 ( en este subárbol, 5 es la raíz y 11, 12 son sus hojas ). De manera similar, se toma en cuenta el máximo de los Nodes 13 y 14 y luego se suma al Node 7. Repita los pasos para cada subárbol hasta llegar al Node.
Sea DP i la suma máxima de valores de Node en el camino entre i y cualquiera de sus hojas moviéndose hacia abajo. Atraviese el árbol utilizando el recorrido DFS . Almacene el máximo de todas las hojas del subárbol y agréguelo a la raíz del subárbol. Al final, el DP 1 tendrá la suma máxima de los valores de los Nodes desde la raíz hasta cualquiera de las hojas sin volver a visitar ningún Node.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ code to find the maximum path sum
#include <bits/stdc++.h>
using namespace std;
vector<int> dp;
// 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 };
// initialise dp
dp = vector<int>(n+1,0);
// 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));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript code to find the maximum path sum
var dp = Array(100).fill(0);
// function for dfs traversal and to
// store the maximum value in []dp
// for every node till the leaves
function dfs(a, v, u, parent)
{
// initially dp[u] is always a[u]
dp[u] = a[u - 1];
// stores the maximum value from nodes
var maximum = 0;
// traverse the tree
for(var child of 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
function maximumValue(a, v)
{
dfs(a, v, 1, 0);
return dp[1];
}
// Driver Code
// Driver Code
var n = 14;
// adjacency list
var v = Array.from(Array(n+1), ()=>Array());
for (var i = 0; i < v.length; i++)
v[i] = [];
// create undirected edges
// initialize the tree given in the diagram
v[1].push(2); v[2].push(1);
v[1].push(3); v[3].push(1);
v[1].push(4); v[4].push(1);
v[2].push(5); v[5].push(2);
v[2].push(6); v[6].push(2);
v[3].push(7); v[7].push(3);
v[4].push(8); v[8].push(4);
v[4].push(9); v[9].push(4);
v[4].push(10); v[10].push(4);
v[5].push(11); v[11].push(5);
v[5].push(12); v[12].push(5);
v[7].push(13); v[13].push(7);
v[7].push(14); v[14].push(7);
// values of node 1, 2, 3....14
var a = [3, 2, 1, 10, 1, 3, 9,
1, 5, 3, 4, 5, 9, 8];
// function call
document.write(maximumValue(a, v));
</script>
22
Complejidad temporal: O(N), donde N es el número de Nodes.