[Algorithm] DP 재활 훈련..

파스칼의 삼각형

---

베이스를 깔아주고

베이스 기반으로 계산하면서 채워준다.
O(N)으로 삼각형 완성

설탕배달

---

배열을 전부 inf 로 채워준 후 dp를 채워준다.

처음부터 바텀업 방식으로 채워주기 때문에 inf가 아닌 값들은 채워질 수 있던 친구들이다.

그렇게 담을 수 있는 친구들이 inf가 아닌 최솟값으로 채워진다.

1로 만들기

---

설탕배달과 동일하다 바텀업 방식으로 위에서 아래로 내리면서 최적값을 찾아준다.

1, 2, 3 더하기

---

경우의 수를 너무 생각하지 말고 더할 수 있는 경우의 수가 1, 2, 3 이 존재한다. 그렇기에 해당 번호의 경우의 수가 dp[i] 에 들어있으니 그 곳에서 1,2,3 을 더해서 만들어지는 3가지 경우의 수가 합쳐진 것이 dp[i]의 값이다.

이친수

---

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

이 조건을 만족하기 위해서 2차원 배열에서 가장 끝자리가 0, 1인 경우의 수를 저장하고 하나씩 추가하는 조건으로 경우의 수를 구했다. 0 은 1,0 둘 다에서 붙일 수 있고, 1은 0에서 밖에 붙이지 못한다.

기본적인 DP 바텀업 코드를 마무리 한다. 다음은 프로그래머스에서 실전을 도전하고 정리해보겠습니다..