e984 - 連假時在做什麼？有沒有空？可以來打code嗎？
題目描述
題目要求找出第 K 個 Lunlun Number。Lunlun Number 的定義是，其十進位表示中，每一位數字與前一位和後一位數字的差值不超過 1。
解題思路
這題使用動態規劃 (DP) 的概念，透過遞迴建表來產生 Lunlun Number。程式碼從 "1" 和 "0" 開始，逐步產生更大的 Lunlun Number。dp 函數遞迴地生成下一個 Lunlun Number，並將其儲存在 ans 陣列中。
核心邏輯是，如果當前數字串的所有位數都是 '9'，則在末尾添加 '1' 並將其他位數設為 '0'。否則，從最高位開始，嘗試將某一位數字加 1，並根據加 1 的結果調整後續位數，以確保滿足 Lunlun Number 的條件。
複雜度分析
- 時間複雜度: O(K * L)，其中 K 是輸入的數字，L 是 Lunlun Number 的最大長度。因為需要生成 K 個 Lunlun Number，且生成每個 Lunlun Number 的時間複雜度與其長度成正比。
- 空間複雜度: O(K * L)，因為需要儲存 K 個 Lunlun Number，每個 Lunlun Number 的長度最長為 L。
程式碼
#include <iostream>
using namespace std;
int k;
string ans[10002]={"0","1"};
void dp(int al,int now){
if(now==10001)return;
bool add=1;
for(int i=0;i<al;++i){
if(ans[now][i]!='9'){
add=0;
}
}
if(add==1){
++now;
ans[now]+="1";
for(int i=0;i<al;++i)
ans[now]+='0';
dp(al+1,now);
return;
}
else{
for(int i=al-1;i>0;--i){
if(ans[now][i]+1<='9'&&abs(ans[now][i]+1-ans[now][i-1])<=1){
ans[now+1]=ans[now];
ans[now+1][i]++;
for(int j=i;j<al;++j)
if(ans[now+1][j]>'0')
ans[now+1][j+1]=ans[now+1][j]-1;
else
ans[now+1][j+1]='0';
dp(al,now+1);
return;
}
}
ans[now+1]=ans[now];
ans[now+1][0]++;
for(int i=0;i<al;++i)
if(ans[now+1][i]>'0')
ans[now+1][i+1]=ans[now+1][i]-1;
else
ans[now+1][i+1]='0';
dp(al,now+1);
return;
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
dp(1,1);
while(cin >> k)
cout << ans[k] << "\n";
}