多發現題目的性質，從性質上下手

dp轉移可以通過更改順序來消除一些限制

把dp轉移需要的條件寫進dp狀態里

dp的用途是廣泛的，包括計數、最優化、可行性等等，其根本就是利用記憶化避免重復計算

• 看到奇怪的限制應該考慮將其形式化，常規化

• 看到位運算類的性質可以考慮數位 dp

• 一個排列的笛卡爾樹唯一，因此關于排列的若干個區間最值限制可以考慮計算笛卡爾樹的形態
  CF1580B Mathematics Curriculum

• 如果元素的貢獻與區間最小最大值有關，那么考慮使用 min-max分治 ，使每個元素在其左右端點不在同一塊的地方被統計，min-max分治 不僅可以計數，也可以求最優化
  P3592 [POI2015] MYJ 【最優化dp】
CF549F Yura and Developers 【計數】

• 階梯型DP優化&pht轉化的巧妙運用
  P6944 [ICPC2018 WF]Gem Island

• 看到要求商最大可以先從 0/1分數規劃 開始想，0/1分數規劃 不一定僅限于每一個物品才會帶來貢獻
  P3778 [APIO2017]商旅

• dp的用途很廣，甚至可以用來防止重復比較等，看到題目不會做先想dp
  P6764 [APIO2020]粉刷墻壁

• DP具有無后效性的體現：構成DP的每一步決策都只與當前的狀態有關，不與前后有關，就比如說給一堆限制，然后可以將這堆限制分類，然后每一類DP，保證在符合之前所有類的限制的情況下滿足當前這一類的限制，可以看做是一種分部處理“且”限制的手段
  P5369 [PKUSC2018]最大前綴和

• 考慮生成一個排列的辦法：狀壓目前使用了多少位，枚舉下一步拓展誰

• 樹形結構很常見，可以用來dp
  SP3734 PERIODNI - Periodni

• 對于樹上任意非祖先兩點的都會對其lca產生限制，就直接按照dfs下去即可，設計狀態的時候直接就是f[i]表示以i為根的子樹中，本身已經滿足限制的狀態，合并的時候考慮不同子樹對于根的限制即可

• 最優化dp 轉移的決策（轉移路徑）不一定要存在直接轉移，只需要保證存在最優（復合）路徑就夠了，就是冗余轉移優化
  P4762 [CERC2014]Virus synthesis

• 如果若干個集合兩兩之間的關系要么包含要么不交，那么集合的包含關系可以構成一棵樹
  CF494C Helping People
P8252 [NOI Online 2022 提高組] 討論 【神仙lsy的集合劃分樹】

• 計數題要考慮如何把問題分組，做到不重不漏，比如可以考慮以最大編號或者最原始祖先來區分等等，就是類似于至少=恰好\(\times\)至少這種，反正選出來的代表要具有 唯一代表性 ，即可以唯一代表一類情況，且分類重不漏
  P7105 「C.E.L.U-01」門禁 【差一點想出來的題】
CF512D Fox And Travelling【自己想出來的題】

• 權值是乘在一起然后開根的，可以把開根看做在指數上除，然后就變成分數規劃問題

• dp 的有效狀態實際上是很少的，可以利用上
  CF1584F Strange LCS

• 如果一些情況使得某一位非常小，某一維非常大（只能接受log），那么可以考慮矩陣乘法

• 01背包的合并具有決策單調性

• 有些題目不能完全預處理，那么就可以先預處理出能預處理的，然后把不能直接預處理出來的用已經預處理的算出來，差不多就是部分預處理
  P4133 [BJOI2012]最多的方案

• 計數類問題考慮加乘法原理
  P5664 [CSP-S2019] Emiya 家今天的飯

• 背包問題決策具有無向性
  P4095[HEOI2013]Eden 的新背包問題

正著做一次，倒著做一次，之后因為無向性就可以把正著做和倒著做的結果合并！！

• 背包問題中交換物品的順序對結果不影響
  P4141 消失之物

• 對于要求元素不重復的dp，設計狀態時可以考慮一個一個的插入元素，過程類似背包

• 計數dp在設計狀態的過程其實是在把情況分類的過程，要注意分類的情況之間相互不包含或重疊，以免在統計時把部分情況算重

• 在讓gcd最大的問題里的一種dp的階段性：把最大的質數作為階段來拓展

• 多個模式串匹配且長度不定的dp可以把模式串放到AC自動機上，接著dp狀態就轉變成匹配到AC自動機上的某個點時的狀態

• 對于dp中的序列問題，如果每個元素的貢獻只與其相對的大小關系有關，那么可以把元素換成康托序，同時一個排列與康托序是一一對應的
  CF1542E1 Abnormal Permutation Pairs (easy version)