사용한 것
- 점화식을 세워 문제를 풀이하기 위한 bottom-up
풀이 방법
dp[i]
의 최대 값은 다음 중 최대 값과 같다.
arr[i] + dp[0]
arr[i - 1] + dp[1]
arr[i - 2] + dp[2]
- 반복....
- 따라서 이중 for문을 사용하여 점화식을 세워
dp[]
를 n
까지 점진적으로 계산하면 된다.
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] line = br.readLine().split(" ");
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(line[i - 1]);
}
int[] dp = new int[n + 1];
dp[1] = arr[1];
for (int i = 2; i <= n; i++) {
for (int j = i; j > 0; j--) {
dp[i] = Math.max(arr[j] + dp[i - j], dp[i]);
}
}
System.out.println(dp[n]);
}
}