JOI 2018 Tents

https://oj.uz/problem/view/JOI18_tents

풀이

dp[h][w] : h개의 행과 w개의 열을 가지고 있을 때, 텐트를 놓을 수 있는 경우의 수

우리는 h번째 행에 중심을 둘 것이다.

1. h번째 행에 아무 텐트도 놓지 않을 경우

2. w개의 열 중에 텐트 하나를 놓을 경우

3. w열 중에 하나 놓고, 하나 놓은 것과 다른 열에 하나를 놓는 경우

4. w열 중에 하나 놓고, 그것과 동일한 열에 h-1개의 행 중 하나를 놓는 경우

1번 같은 경우엔 점화식은 

2번 같은 경우엔 점화식은 

3번 같은 경우엔 점화식은 

4번 같은 경우엔 점화식은 

점화식이 나와있으니 스무스하게 탑다운으로 짜면 그냥 머 뚝딱

하나 조심해야 하는 부분은 다 비어있는 경우를 제외해야 한다. 최종답 - 1을 해주면 답

코드

https://oj.uz/submission/49323