arr = new int[N+1][M+1];
cache = new int[N+1][M+1];

for(int i = 1; i <= N ; i++){
for(int j = 1; j <= M; j++){
arr[i][j] = sc.nextInt();
}
}

for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
int result = 0;
result = Math.max(cache[i-1][j-1], Math.max(cache[i-1][j], cache[i][j-1]));
cache[i][j] = result + arr[i][j];
}
}

System.out.println(cache[N][M]);


위의 식으로는 풀렸는데


아래와 같이 재귀를 이용해서 풀 경우는 시간초과가 발생하더군요.


아래와 같이 재귀의 경우 DP가 아닌것인지 궁금합니다.


hihihi   1달 전

메모이제이션이라고 부릅니다

댓글을 작성하려면 로그인해야 합니다.