[알고리즘/C++] 동적계획법 - 최대 값의 경로 찾기

2차원의 공간이 주어지고 각 인덱스의 공간마다 특정 값(Value)가 주어진다. 가장 상단 왼쪽의 격자부터 가장 하단 오른쪽의 격자로 이동하면서 경로 상의 값이 총합이 최대가 되도록 하는 알고리즘을 동적 계획법으로 풀어보자. 이동 조건은 오른쪽 혹은 아래 방향으로만 움직인다는 것이다. 1 2 1 2 0 1 3 4 5 6 1 2 3 5 1 위의 예시에서는 1 2 1 2 0 1 3 4 5 6 1 2 3 5 1 위의 경로로 이동하는 것이 최대값을 가진다. int maxSumRoute(vector arr) { vector sum(arr.size(), vi(arr[0].size(), 0)); for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].si..

2023.07.28