# 輪廓線 DP（插頭 DP）

> 名字可能聽起來很酷（很難懂）但其實初步理解它不會很難

主要是看了 USACO Guild https://usaco.guide/adv/dp-more?lang=cpp#dp-on-broken-profile

## 目標

- 處裡一些 2D 方格的連通問題
- 通常給的圖，其中一個維度（Diamenson）遠小於另一個
- 大概是 10~12 超適合做位元 DP！！
- 一個格子的狀態只與相鄰方格有關
- 很像 DP 的性質

例題：https://cses.fi/problemset/task/2181

## 輪廓線

這題的輪廓線就是長這樣（非灰色的所有格子）

應該蠻好解讀的

## 核心

重點就是轉移的過程，因為目前要填 i,j 這個位置，我們自己又先定義了如果目前處裡到 i,j，那麼 i,j 前面的格子都要是放好的（也可以視為都已經算好方法數），所以 i,j 就只有兩種填法
1. 填直的
2. 填橫的

假設現在處裡的是這一格

那麼 這一個就有兩個被填到的方法
1. 
2. 

第一次看到可能會想說，第一個很合理，畢竟那一格的狀態就在輪廓線上，但第二格沒有。
但這邊要釐清一個概念，DP 的轉移都是從上一格過來的，所以第二種填法很合理可以讀取到那一格的狀態。

在閱讀 USACO 上的程式碼時，要注意：
1. 他是用滾動 DP，所以有些會比較難懂一點
2. L:15 要稍微去理解一下為什麼