推 scott0002: 直覺 backtracking 剪枝 不過不知道是 114.137.75.101 12/18 14:03
→ scott0002: 不是100%可行 114.137.75.101 12/18 14:03
→ scott0002: 我看錯題目了 114.137.75.101 12/18 14:04
求職時線上測驗的問題，有算出解答，但覺得應該有更好的解法，
向各位版友請教解題想法。
問題如下：
一個七位數的數字，從第七位到個位數的順序開始比對。
若當前位數的值，不小於曾出現過的數的最大值，就記錄起來。
請問紀錄結果為四個數字的可能組合數有幾組？
例：
2334849 - 由左至右
第一位數 2 加入紀錄
第二位數 3 大於等於2，加入紀錄
第三位數 3 大於等於3，加入紀錄
第四位數 4 大於等於3，加入紀錄
第五位數 8 大於等於4，加入紀錄
第六位數 4 不紀錄
第七位數 9 大於等於8，加入紀錄
紀錄結果為 6
6429748 - 紀錄 69 （2個數）
4629889 - 紀錄 4699（4個數）
各位數可以為 0，例如 0001234、0007899 也符合要求。
我用迴圈跑 1~一千萬涵蓋七位數，每個數字都檢查紀錄結果，得出組數。
跑了五分多鐘，很笨也很沒有效率。
想請問是否有更效率的解題方式？
請大家指教，感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.121.223.216 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1598856385.A.8D2.html