SK_MOUSE 개발일기

동적프로그래밍(Dynamic Programming)의 기본형이 되는 문제이다. Math.max값을 이용하여 이전 인덱스의 값과 비교하여 주어진 배열에 직접 업데이트 하는 방식이다. import java.util.Arrays; class Solution { public int solution(int[][] triangle) { int answer = 0; for (int height = 1; height < triangle.length; height++) { for (int i = 0; i < triangle[height].length; i++) { if (i == 0) {//맨왼쪽 triangle[height][0] += triangle[height - 1][0]; } else if (i == trian..

재귀함수형태로 점화식이 생기는 문제에서 일대일함수임이 만족될때 각 함수의 파라미터를 키로 결과를 캐싱하는걸 dp라함 이때 캐싱하는 자료구조를 편의상 상태공간이라 부르는데 별 의미는 없고 동적계획법(Dynamic programming)은 자료구조에서 동적할당(Dynamic Allocation)과는 다르다. 알고리즘에서 사용되는 "다이나믹(Dynamic)"은 별다른 의미 없이 사용된 단어이다. 다이나믹 프로그래밍 문제인지 확인하려면 아래 조건을 만족하는지 확인하면 된다. 1. 최적 부분구조(Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은..