這次我們照樣看一道題。個人認為比上一次的簡單。
https://vijos.org/p/1130
先說方法，動态規劃，你能想到什麼？
“在它的左邊加上一個自然數，但該自然數不能超過原數的一半”
是以，如果一個數i左邊可以加上的數記作dp[i]，那麼，左邊可以加上的數一共是從1到i/2的情況，也就是dp[1]+...+dp[i/2]。
再算上“什麼也不加”的情況，我們很容易得出：
dp[i]=1+dp[1]+dp[2]+...+dp[i/2]
同時，dp[1]=1，那麼我們可以寫程式了：
這次我們照樣看一道題。個人認為比上一次的簡單。
https://vijos.org/p/1130
先說方法，動态規劃，你能想到什麼？
“在它的左邊加上一個自然數，但該自然數不能超過原數的一半”
是以，如果一個數i左邊可以加上的數記作dp[i]，那麼，左邊可以加上的數一共是從1到i/2的情況，也就是dp[1]+...+dp[i/2]。
再算上“什麼也不加”的情況，我們很容易得出：
dp[i]=1+dp[1]+dp[2]+...+dp[i/2]
同時，dp[1]=1，那麼我們可以寫程式了：