반응형
정수삼각형
-
알고리즘: 백준 1932번 정수 삼각형 (feat. Python)알고리즘/백준(BaekJoon) 2020. 7. 22. 07:21
최적 부분 구조와 중복되는 부분이 보인다. 다이나믹 프로그래밍으로! 점화식: n 번째 줄 0번째까지의 합 = n - 1번째 줄 0번째까지의 합 + n 번째 줄 0번째 값 n 번째 줄 1번째까지의 합 = max(n - 1번째 줄 0번째까지의 합, n - 1번째 줄 1번째까지의 합) + n번째 줄 1번째 값 n 번째 줄 2번째까지의 합 = max(n - 1번째 줄 1번째까지의 합, n - 1번째 줄 2번째까지의 합) + n번째 줄 2번째 값 ... n 번째 줄 n - 1번째까지의 합 = max(n - 1번째 줄 n - 2번째까지의 합, n - 1번째 줄 n - 1번째까지의 합) + n번째 줄 n - 1번째 값 n 번째 줄 n번째까지의 합 = n - 1번째 줄 n - 1번째까지의 합 + n 번째 줄 n번째 값..