幾個常見的DP類型.

幾個常見的DP類型.

例題1.P1216 [USACO1.5][IOI1994]數字三角形 Number

本題每個點路徑選擇隻有兩種，很好寫dp，具體解釋見下面代碼。

2.The least round way

思路：考慮對答案的貢獻有因數2，5，0.對于0我們隻需找到一個标記位置即可（它對答案貢獻一個0），對于（2，5）我們隻需要比較兩者到達終點的較小值，即為0的貢獻。

而找2，5，的貢獻可以用dp實作。列印可用遞歸實作。

下面上代碼。本題主要考點（數論+路徑DP）

3.過河卒

路徑DP+滾動數組壓縮狀态 下面上兩種代碼。

不壓縮狀态

壓縮狀态

P2837 [USACO08FEB]Dining Cows B

假設dp[i]為前 i 頭 牛的最小修改數。 對第 i 頭 牛 進行讨論。如果 第 i 頭牛為 2 不用管：dp[ i ]=dp[i -1] ,如果第i頭牛為1 又分兩種情況：1.如果不用修改，dp[ i ]則等于前面 2 的個數 ， 2.如果要修改，則等于dp[i-1] +1, cnt 可以用一維，由于 dp[ i ] 是由前一個狀态的得到，是以空間都可以壓縮為 O（1）。下面見代碼。

P1877 [HAOI2012]音量調節

設dp[ i] [j] 第i首歌能到達的音量 j ， dp[ i ] [ j ] =1表示該狀态能到達 ，反之為0不能到達，最後粗從大到小掃一遍即可。