今天開始做關于數位DP的問題，首先對于數位DP來說，這類問題難度較大，比較難理解，所以博主也會盡量講的更加詳細一些，來幫助大家更好地理解這里的相關知識。
前置知識：
1.首先對于數位DP來說，主要解決的是關于在一段數的范圍里，求解所含特殊條件的字符的數的個數。例如在[1,100]之間尋找包括7的數字個數。
2.數位dp的dp數組一般設置為dp[pos][snt][cnt]，其中pos表示數字代表的位數，snt表示當前位數是否合法，cnt表示數位合法的個數。
3.一般數位dp中有bool形的limit參數，當limit=true時表示對當前數位有限制，后面的數字不能不能直接使用0-9作為處理，當limit=true時是不能用來做記憶化處理的。
從前有一個國王，他十分熱愛數字，他認為數字的優雅程度可以從它們的位數上體現出來。數字的“優雅程度”越高，就越能夠吸引他的眼球。他定義，只要一個正整數的十進制表示中包含不超過 3 個非零數字，就被認為是優雅的數字。例如，3、2000、123 是優雅的數字，而 4321、12306、120086 則不是。
這個國王曾經讓他的數學家尋找一定范圍內所有的優雅數字。但這些數學家并不滿足于簡單地列出這些數字，他們想要創造一個故事，使得這些數字更加有生命力、更加有意義。于是他們提出了一個挑戰：給出一個數字區間，計算其中有多少個優雅的數字。你能夠幫助這些數學家完成他們的任務嗎？
輸入格式
輸入包含多個測試用例。
每個測試用例的第一行包含一個整數?T (1≤T≤102)，表示要考慮的數字區間的數量。
接下來?T?行，每行包含兩個整數 Li??和?Ri? (1≤Li?≤Ri?≤1018)，表示一個區間的左右端點。
輸出格式
對于每個測試用例，輸出一個整數，表示相應區間中優雅數字的數量。
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
ll dp[20][2][20];
int a[20];
ll dfs(int pos,bool snt,bool limit,int cnt){if(pos<0)return (int)(cnt<=3);if(!limit&&dp[pos][snt][cnt]!=-1)return dp[pos][snt][cnt];ll res=0;int up=limit?a[pos]:9;for(int i=0;i<=up;i++){res+=dfs(pos-1,snt||(i>0),limit&&(i==up),cnt+(i>0));}if(!limit)dp[pos][snt][cnt]=res;return res;
}ll f(ll b){int pos=0;while(b){a[pos++]=b%10;b/=10;}return dfs(pos-1,false,true,0);
}
int main()
{int t;cin>>t;while(t--){memset(dp,-1,sizeof(dp));ll a,b;cin>>a>>b;cout<<f(b)-f(a-1)<<'\n';}return 0;
}
分析
1.在數位動態規劃中，return (int)(cnt <= 3)?這行代碼是遞歸終止條件的核心邏輯，其作用是判斷當前構造的數字是否符合 “優雅數字” 的定義。當?pos < 0?時，表示已經處理完數字的所有位（例如，對于三位數?123，pos?從最高位?2?遞減到?0，處理完最低位后?pos?變為?-1）。此時，遞歸需要返回一個結果，用于統計符合條件的數字數量。
2.為什么?limit == true?時不能記憶化？
假設我們正在處理數字?123，并遞歸到百位為?1（最高位）的狀態：
此時?limit == true，百位只能選?0?或?1。若百位選?0，后續的十位和個位可以任意選（0-9）；若百位選?1，后續的十位只能選?0-2（受原數字?123?的限制）。
如果我們在?limit == true?時記錄了這個狀態的結果，當處理其他數字（如?456）時，同樣的狀態（例如?pos=2, st=true, cnt=1）可能會復用錯誤的結果（因為?456?的百位可以選?0-4，與?123?的限制不同）。
3.snt的作用：處理前置0，一般的數位dp中都會有snt用來處理前置0，但本道題因為都是正整數，所以并沒有處理前置0.
4.記憶化的本質：記錄已計算的狀態結果
關鍵點：dp[pos][st][cnt]?存儲的是當前狀態在無限制（limit=false）時的結果。這個結果是在枚舉完當前位的所有可能取值并計算出總和后才能確定的，因此必須在遞歸調用結束并累加到?res?之后才能記錄。
今天的分享就到這里，關于這個類型的dp是比較難以理解的，希望大家可以收藏做做，麻煩大家多多關注，后續博主也將繼續分享相關的內容。
