板子

?? DP(pos,狀態(tài)變量...,限制布爾){if(pos==0)return 1;//一般每次執(zhí)行到這里時(shí)的數(shù)是要算入總結(jié)果的 不一定是1 根據(jù)題目確定if(!limit&&dp[對(duì)應(yīng)狀態(tài)]!=-1)return dp[對(duì)應(yīng)狀態(tài)]; //記憶化搜索int up = limit?d[pos]:9;//表示如果前面一位有限制 就說明這是擦著區(qū)間上界走的 需要返回d[pos] 如果沒有限制 說明沒臨界 返回9ll a=0;for(int i=0;i<=up;i++){if()...else if()...//針對(duì)不同的題目設(shè)置不同的變量記錄函數(shù)a+=(pos,狀態(tài)變量...,限制布爾&&i==d[pos]);//如果這兩個(gè)條件都有再傳遞}if(!limit)dp[狀態(tài)]=a;//已經(jīng)求出對(duì)應(yīng)狀態(tài)值下的結(jié)果了 記錄下來return a;}

所以 數(shù)位dp其實(shí)就是一種求解有關(guān)于l到r有多少個(gè)符合條件的數(shù)目類似的統(tǒng)計(jì)問題的解題思路
一遍遍數(shù)字枚舉太慢

不如我們根據(jù)條件枚舉數(shù)位
數(shù)位dp本質(zhì)上是記憶化搜索

我們需要在數(shù)位上進(jìn)行遞推
把條件篩選融入到數(shù)位上的篩選
所以數(shù)位dp其實(shí)就是一種算法策略可以讓我們
記憶化地去搜索我們想要得到的數(shù)據(jù)結(jié)果

我們把這個(gè)數(shù)位給他拆開一位一位的枚舉
根據(jù)題目對(duì)應(yīng)的約束條件 設(shè)置記錄結(jié)構(gòu)
一般把對(duì)應(yīng)長度，其余位數(shù)符合什么什么條件的 并且沒有限制的數(shù)目記錄下來
以供我們之后搜到相同的狀態(tài)重復(fù)利用數(shù)據(jù)
降低搜索分支

總結(jié)

以上是生活随笔為你收集整理的数位dp 模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。