CCF 201312-4 有趣的數 python 滿分

• 題目叙述
• • 問題描述：略
  • 輸入格式：略
  • 輸出格式：略
  • 樣例
• 滿分證明
• 解題思路
• 滿分代碼
• 感謝及參考博文

題目叙述

問題描述：略

輸入格式：略

輸出格式：略

樣例

樣例輸入
4

樣例輸出
3
           

滿分證明

解題思路

這是一個動态規劃問題（Dynamic Programming，簡稱DP問題），這也是我做的第一道動态規劃問題（動态規劃問題是将大問題拆解成多子問題然後各個擊破，有逆向思維的味道，常借助存儲資料表實作）。如有不足之處，還請各位看官多多指教(#^.^#)！

1. 通過分析題幹中的條件，我們可以知道首位一定是2；

2. 在不考慮題幹中條件1時，可将其拆分為六種狀态：

   狀态0：隻含有2；

   狀态1：隻含有2和0；

   狀态2：隻含有2和3；

   狀态3：隻含有2、0和3；

   狀态4：隻含有2、0和1；

   狀态5：含有四種數字。

3. 使用 dp[i][j] 來表示滿足該狀态的數值個數，其中i表示整數個數，j表示狀态值，即有：

   #狀态0隻含有2，故為1
   dp[i][0]=1
   #狀态1可由“上一個整數個數”的狀态0後面加2，也可由“上一個整數個數”的狀态1後面加0或2
   dp[i][1]=dp[i-1][0]+dp[i-1][1]*2
   #狀态2可由“上一個整數個數”的狀态0後面加3，也可由“上一個整數個數”的狀态2後面加3
   dp[i][2]=dp[i-1][0]+dp[i-1][2]
   #狀态3可由“上一個整數個數”的狀态1後面加3，也可由“上一個整數個數”的狀态2後面加0，//
   #也可由“上一個整數個數”的狀态3後面加3或0
   dp[i][3]=dp[i-1][1]+dp[i-1][2]+dp[i-1][3]*2
   #狀态4可由“上一個整數個數”的狀态1後面加1，也可由“上一個整數個數”的狀态4後面加1或2
   dp[i][4]=dp[i-1][1]+dp[i-1][4]*2
   #狀态5可由“上一個整數個數”的狀态3後面加1，也可由“上一個整數個數”的狀态4後面加3，//
   #也可由“上一個整數個數”的狀态5後面加3或1
   dp[i][5]=dp[i-1][3]+dp[i-1][4]+dp[i-1][5]*2
              

4. 如果全部了解了上面内容，則題中所要求的即為dp[i][5]。

注意：

由于答案可能非常大，隻需要輸出答案除以1000000007的餘數（這個可是值80分哦）。

滿分代碼

n = eval(input())
dp = c = [[0] * 6 for _ in range(1000)]

mod = 1000000007

def cal(p):
    """
    0--->2
    1--->2 0
    2--->2 3
    3--->2 0 3
    4--->2 0 1
    5--->四種
    """
    for i in range(1, p + 1):
        dp[i][0] = 1
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 2) % mod
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][2]) % mod
        dp[i][3] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] * 2) % mod
        dp[i][4] = (dp[i - 1][1] + dp[i - 1][4] * 2) % mod
        dp[i][5] = (dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] * 2) % mod
    return dp[p][5]

print(cal(n))

           

感謝及參考博文

部分内容參考以下連結，這裡表示感謝 Thanks♪(･ω･)ﾉ

參考博文1 CCF 201312-4 有趣的數(數位DP)

https://blog.csdn.net/jiange_zh/article/details/50300655

參考博文2 CCF 201312-4 有趣的數

https://blog.csdn.net/gengli2017/article/details/82666188

需者自取傳送門(∩ᄑ_ᄑ)⊃━☆【CCF 2013-2021】本部落客整理曆年至少前兩題 python 滿分代碼目錄