快饿死的XzzF(问题一分为二，再用动态规划)

野性酷女 2023-01-13 01:49 71阅读 0赞

https://ac.nowcoder.com/acm/problem/14714  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]  
代码是猜的，没想到过了，灵感来自斐波那契数列。

#include<bits/stdc++.h>
    using namespace std;
    
    void sovle()
    { 
        int n;
        cin >> n;
        long long dp[25];
        memset(dp,0,sizeof(dp));
        dp[1] = 2;
        dp[2] = 3;
        for(int i = 3; i <= n; i++){ 
            dp[i] = dp[i-1] + dp[i-2];
        }
        cout << dp[n];
        
    }
    
    int main()
    { 
        sovle();
        return 0;
    }

**动态规划题解：**

f \[ i \] \[ 1 \] f\[i\]\[1\] f\[i\]\[1\]:表示第i位，放1的方案数  
 f \[ 1 \] \[ 0 \] f\[1\]\[0\] f\[1\]\[0\]:表示第i位，放0的方案数  
状态转移方程：  
(1)  
**0 的前面必是1**  
所以 f \[ i \] \[ 0 \] = f \[ i − 1 \] \[ 1 \] f\[i\]\[0\] = f\[i-1\]\[1\] f\[i\]\[0\]=f\[i−1\]\[1\]  
(2)  
**1的前面可以是1，也可以是0**  
所以  
 f \[ i \] \[ 1 \] = f \[ i − 1 \] \[ 0 \] + f \[ i \] \[ 1 \] f\[i\]\[1\] = f\[i-1\]\[0\] + f\[i\]\[1\] f\[i\]\[1\]=f\[i−1\]\[0\]\+f\[i\]\[1\]

ac代码：

#include<bits/stdc++.h>
    using namespace std;
    long long dp[25][3];
    void sovle()
    { 
        int n;
        cin >> n;
        dp[1][0] = 1;
        dp[1][1] = 1;
        for(int i = 2; i <= n; i++){ 
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][1] + dp[i-1][0]; 
        }
        cout << dp[n][0] + dp[n][1];
        
    }
    
    int main()
    { 
        sovle();
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221022/261fb548fe46431281d84b4b729f920b.png