APCS201802第4題階梯數字

TCIRC：https://judge.tcirc.tw/ShowProblem?problemid=d080

參考：https://home.gamer.com.tw/artwork.php?sn=4311599

一個正整數如果從高位數往低位數看過去，每一位數字只會相等或變大，則我們稱它為階梯數字，例如：9、234、777、11222233。

給定一正整數 N，請計算不大於 N的階梯數字總共有幾個，請注意本題只算正整數，所以 0 不算階梯數字，而且階梯數字不會以 0 開始。

輸入說明

輸入一個正數字 N。

N <= 1e18。

輸出說明

不大於 N 的階梯數字個數。

輸入範例1

25

輸出範例1

22

輸入範例2

101

輸出範例2

54

解題策略

查表，DP，類似巴斯卡三角形，建立dp[長度][開頭數字]的階梯數字個數