다이나믹 프로그래밍

dp[i]는 항상 누적값

피보나치 함수

풀이

[기본]
function solution() {
   let n = 3
   
   let zero = 0;
   let one = 0;
   
   function fibo(n) {
       if (n === 0) {
           zero++
           return 0
       } else if (n === 1) {
           one++
           return 1
       } else {
           return fibo(n-1) + fibo(n-2)
       }
   }    
       fibo(22)
       console.log(zero, " ", one)
}

[상향식]
function solution() {
   let n = 3
   
   let d = new Array(100).fill(0)
   
   d[0] = 0
   d[1] = 1
   
   for (let i=2; i<=40; i++) {
       d[i] = d[i-1] + d[i-2]
   }
   
   console.log('전체', d) // 40까지의 피보나치 수
    
   // 만약 주어진 n이 0이라면 0한 개, 1한 개이므로
   if (n == 0) console.log(1, 0)
   else console.log(d[n-1], d[n])
   
//  n이 3일 때 실행 결과
//     d[2], d[3]
//     d[2] = d[1] + d[0] : 1 + 0 = 1
//     d[3] = d[2] + d[1] : 1 + 0 + 1 = 2
//     d[4] = d[3] + d[2] : 2 + 1 = 3
}		

설명

가장 기본적인 점화식 문제 우리는 zero와 one의 갯수를 구하는 것이기 때문에 주어진 변수로 0일 때와 1일 때를 카운트해서 주면 된다.
여기서 실수할 수도 있는 부분은 else에 관한 부분인데, else에는 아무처리를 안 해도 자동으로 0과 1에 도달하므로 괜찮은 걸 볼 수 있다.

---

01타일

출력시 15746으로 나누는이유는 값이 너무 커질까봐

풀이

값을 생각해보면 피보나치의 모습을 띄고 있다. (직접 만들어 보면 됨)
그것을 갖고 메모이제이션을 통한 배열을 만들고 그 배열에 n+1값을 구해주면 됨

function solution() {
    let n = 4
    
    let d = new Array(100).fill(0)
    
    d[0] = 0
    d[1] = 1
    
    for (let i=2; i<=40; i++) {
        d[i] = d[i-1] + d[i-2]
    }
    
    console.log('전체', d) // 40까지의 피보나치 수
    
    if (n == 0) console.log(1, 0)
    else console.log(d[n+1])
    
}

---

*포도주 시식 ★

풀이

1. i번째를 마시지 않는다

-> 그렇다면 dp에 저장된 값중에 자기보다 한 개 작은 애보다는 클 거니까 dp[i-1]

2. i번째를 마신다

-> 1. 본인만 마심 : 본인의 양 + 본인 2개 전까지의 양
dp[i] = arr[i] + dp[i-2]
얘가 두 개만 있는 이유는, 어떻게 됐던 dp[i-2]가 dp[i-3]보다 크고, 그 친구까지 포함한 값이니까 가장 큰 자신과 + 자기의 한 개 띄우고 다음 애까지인 것

-> 2. 본인과 본인 전 까지 마심 : 본인의 양 + 본인 전의 양 + 본인 3개전까지의 양
dp[i] = arr[i] + arr[i-1] + dp[i-3]

function solution() {
    let n = 6;
    let arr = [6, 10, 13, 9, 8, 1]
    
    
    let dp = new Array(n).fill(0)
    dp[0] = arr[0]
    dp[1] = arr[0] + arr[1]
    dp[2] = Math.max(arr[0] + arr[1], arr[1] + arr[2], arr[0] + arr[2])
    
    
    for (let i=3; i<n; i++) {
        dp[i] = Math.max(dp[i-1], arr[i]+dp[i-2], arr[i]+arr[i-1]+dp[i-3])
    }
    
    console.log(dp)
    console.log(dp[n-1])    
}

---

파도반 수열

풀이

초반에 주어진 P로 점화식을 구현하고 규칙을 찾으면 쉬운 문제

function solution() {
    let n = 12
    // let p = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
    // 2+3, 5
    let dp = new Array(n).fill(0)
    
    dp[0] = 1
    dp[1] = 1
    dp[2] = 1
    
    for (let i=3; i<n; i++) {
        dp[i] = dp[i-3] + dp[i-2]
    }
    
    console.log(dp[n-1])
}

정수 삼각형

풀이

function solution() {
    let n = 5
    let dp = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
    
    let right = 0;
    let left = 0;
    
    // i는 1, j는 0부터 i까지 두어 2번 반복 전체의 값을 찾는 게 아닌
    // 해당 하는 애의 왼쪽 아래, 오른쪽 아래만 보면 됨
    for (let i=1; i<n; i++) {
        for (let j=0; j<=i; j++) {
            // 왼쪽 위
            let upLeft = 0;
            if ( j !== 0) upLeft = dp[i-1][j-1];
            
            // 바로 위
            let up = 0;
            if ( j !== i) up = dp[i-1][j];
            
            // 최대값을 다음 인덱스에 계속 추가해 나가며
            dp[i][j] += Math.max(upLeft, up)
        }
    }
    
    console.log(dp)
    console.log(Math.max(...dp[n-1]))
}