algorithm
최대 경로 합계 알고리즘
수색…
최대 경로 합계 기본 정보
최대 경로 합은 해당 경로의 요소 (노드) 합계가 다른 경로보다 큰 경로를 찾는 알고리즘입니다.
예를 들어 아래 그림과 같이 삼각형을 만듭니다.
3
7 4
2 4 6
8 5 9 3
위 삼각형에서 최대 합계를 갖는 최대 경로를 찾으십시오. 답은 3 + 7 + 4 + 9 = 23
해결책을 찾으려면 항상 Brute-Force 방법에 대한 아이디어를 얻으십시오. Brute-Force 방법은이 4 행 삼각형에 적합하지만 100 행 또는 100 행 이상의 삼각형에 대해 생각하십시오. 그래서 우리는 Brute-Force 방법을 사용하여이 문제를 해결할 수 없습니다.
동적 프로그래밍 접근법으로 넘어 갑시다.
연산:
삼각형 또는 이진 트리의 각 노드마다 최대 경로가 노드를 통과하는 네 가지 방법이 있습니다.
- 노드 전용
- Left Child + Node를 통한 최대 경로
- 오른쪽 자식 + 노드를 통한 최대 경로
- 왼쪽 하위 노드 + 노드 + 오른쪽 경로를 통한 최대 경로.
최대 경로 합산 알고리즘의 예 :
우주 보조 장치 : O(n)
시간 복잡성 : O(n)
C # 구현
public class Node
{
public int Value;
public Node Left, Right;
public Node(int item)
{
Value = item;
Left = Right = null;
}
}
class Res
{
public int Val;
}
public class MaximumPathSum
{
Node _root;
int FindMaxUtil(Node node, Res res)
{
if (node == null) return 0;
int l = FindMaxUtil(node.Left, res);
int r = FindMaxUtil(node.Right, res);
int maxSingle = Math.Max(Math.Max(l, r) + node.Value, node.Value);
int maxTop = Math.Max(maxSingle, l + r + node.Value);
res.Val = Math.Max(res.Val, maxTop);
return maxSingle;
}
int FindMaxSum()
{
return FindMaxSum(_root);
}
int FindMaxSum(Node node)
{
Res res = new Res {Val = Int32.MinValue};
FindMaxUtil(node, res);
return res.Val;
}
public static int Main()
{
MaximumPathSum tree = new MaximumPathSum
{
_root = new Node(10)
{
Left = new Node(2),
Right = new Node(10)
}
};
tree._root.Left.Left = new Node(20);
tree._root.Left.Right = new Node(1);
tree._root.Right.Right = new Node(-25)
{
Left = new Node(3),
Right = new Node(4)
};
return tree.FindMaxSum();
}
}
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow