[TIL] DP 알고리즘 공부

가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

DP 알고리즘

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const [n, test] = input

const list = test.split(' ').map((x) => +x)
const dp = []
for (let i = 0; i < +n; i++) {
	dp.push(1)
}

for (let i = 1; i < +n; i++) {
	let max = 0
	for (let j = 0; j < i; j++) {
		if (list[j] < list[i]) {
			if (dp[j] > max) {
				max = dp[j]
			}
		}
	}
	dp[i] = max + 1
}

console.log(Math.max(...dp))

참고
https://bitwise.tistory.com/215
https://wootool.tistory.com/96

계단 오르기

https://www.acmicpc.net/problem/2579

DP 알고리즘

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const [n, ...tests] = input
const score = tests.map((x) => +x)

const dp = new Array(+n).fill(0)

dp[0] = score[0]
dp[1] = score[0] + score[1]
dp[2] = Math.max(score[0] + score[2], score[1] + score[2])

for (let i = 3; i < +n; i++) {
	dp[i] = Math.max(dp[i - 3] + score[i - 1] + score[i], dp[i - 2] + score[i])
}

console.log(dp[+n - 1])