#2 Dynamic Programming

probability dp(확률 dp)

확률과 기댓값은 다르다.

 

ex)

1. 정육면체 주사위를 던질 때 1이 나올 확률?

1/6

2. 정육면체 주사위를 던질 때 1이 나올 때까지 던지는 횟수의 기댓값은? = 6

1번 던졌을 때 1이 나올 확률(1/6)

+ 2번 던졌을 때 1이 나올 확률(5/6(1이 처음에 안나올 확률) * 1/6(1이 그다음에 나올 확률) * 2)

+ 3번 던졌을 때 1이 나올 확률

(5/6(1이 처음에 안나올 확률) * 5/6(1이 두번째 던졌을때도 안나올 확률) * 1/6(1이 나올 확률) * 3)

+ ......

다음과 같은 식으로 표현할 수 있다.

 

 

3. 정육면제 주사위를 던질 때 나온 수의 기댓값은?

(1/6 * 1) + (1/6 * 2) + (1/6 * 3) + (1/6 * 4) + (1/6 * 5) + (1/6 + 6)

 

Tree dp

tree는 cycle이 없는 연결된 그래프

예시 문제

백준 15681 (트리와 쿼리) c++

 

 

bit dp

bit를 활용하는 dp 형태 

n개의 bit로 표현할 수 있는 수는 총 2^n 인걸 이용해서, 

n<=20 일때, dp[n] = n의 i번째 bit가 켜져 있으면, i번째 값이 선택 되어 있는 상태

주어진 문제 에서 n이 작을 때 위와 같이 dp를 정의하면 dp로 쉽게 풀리는 문제들이 존재한다.

예시 문제

백준 2098 (외판원 순회) c++