想了一個遞迴DP
因為這是一個取或不取的問題 很適用遞迴法
基本型態會是 f(n) = g(f(n-1), f(n-2), ... ) 這樣 g()通常是min或sum或if-else
可以系統化來寫這3個步驟:
1. 寫遞迴式
2. 寫終止條件
3. 寫查表
以這題來說 可以寫一個遞迴 rec(0,0,0) :
// pos:第幾位, prev:上次的數字, acc:目前取幾位了
int rec(int pos, int prev, int acc) {
// 遞迴式
int ret = 0;
for (int i = 0; i < 10; ++i) {
if (i >= prev)
ret += rec(pos+1, i, acc+1); // 要這位數
else
ret += rec(pos+1, prev, acc); // 不要這位數
}
return ret;
}
那麼再來就是終止條件 我想了3個:
int rec(int pos, int prev, int acc) {
// 終止條件
if (acc > 4) return 0; // 取超過了
if (pos > 6) return acc == 4; // 到底了是否剛好取到4個
if ((7 - pos) + acc < 4) return 0; // 不夠取了
// 遞迴式
...
}
到這應該就可以運作了 以c++ code來說其實已經夠快
不過這樣還沒用到查表
於是直接把整個rec的參數拿來當key:
struct S {
int pos, prev, acc;
bool operator<(const S &o) const {
if (pos != o.pos) return pos < o.pos;
if (prev != o.prev) return prev < o.prev;
return acc < o.acc;
}
};
static map<S, int> cache;
int rec(int pos, int prev, int acc) {
// 終止條件
...
// 查表
auto iter = cache.find({pos,prev,acc});
if (iter != cache.end()) return iter->second;
// 遞迴式
...
cache[{pos,prev,acc}] = ret;
return ret;
}
這樣就完成啦
答案是2027025 (希望是對的)
時間的話 在我電腦上直接暴力解是0.75秒 純遞迴是0.063 加DP是0.017
看起來似乎合理
※ 引述《applebeing (蘋果人)》之銘言：
: 求職時線上測驗的問題，有算出解答，但覺得應該有更好的解法，
: 向各位版友請教解題想法。
: 問題如下：
: 一個七位數的數字，從第七位到個位數的順序開始比對。
: 若當前位數的值，不小於曾出現過的數的最大值，就記錄起來。
: 請問紀錄結果為四個數字的可能組合數有幾組？
: 例：
: 2334849 - 由左至右
: 第一位數 2 加入紀錄
: 第二位數 3 大於等於2，加入紀錄
: 第三位數 3 大於等於3，加入紀錄
: 第四位數 4 大於等於3，加入紀錄
: 第五位數 8 大於等於4，加入紀錄
: 第六位數 4 不紀錄
: 第七位數 9 大於等於8，加入紀錄
: 紀錄結果為 6
: 6429748 - 紀錄 69 （2個數）
: 4629889 - 紀錄 4699（4個數）
: 各位數可以為 0，例如 0001234、0007899 也符合要求。
: 我用迴圈跑 1~一千萬涵蓋七位數，每個數字都檢查紀錄結果，得出組數。
: 跑了五分多鐘，很笨也很沒有效率。
: 想請問是否有更效率的解題方式？
: 請大家指教，感謝！