算法學習之路|數位dp簡要分析

數位dp一般用于處理一些和數位有關的計數問題，比如說求區間[l,r]中有多少符合條件的數，而為了減少時間複雜度，方法使用的是動态規劃的思想。

舉例說明：問從0到2345這些數中總共包含多少6。

數位dp的思路是：

1.由于千位是2，首先求出[0,2000)中滿足條件的個數，因為此時個十百位可以任意取值，不受上界的限制。

2.之後由于千位已經到達最高，要改為考慮百位，此時百位受到上界的限制，是以之後需要求出[2000,2300)中馬滿足條件的個數，此時十位和個位不受限制。

3.當百位是3時，十位又受到限制…以此類推。

當然，如何計算一個整百整千的區間的滿足條件的個數，也需要在代碼中展現，比如這裡f(2000)=2f(1000)=2(100+10f(100))=2(100+10(10+10f(10)))

以下是數位dp的模闆：

例題：

所有含有4或者含有62的數都是不吉利的，求一定範圍内有多少吉利的數。

ac代碼：