洛谷P1990 覆盖墙壁（递推、dp）

题目来源：https://www.luogu.com.cn/problem/P1990

经典递推，代码很短所以放这了，但是递推或dp的初学时会很难想这个思路：
`#include

define int long long

using namespace std;
int dp[1000010][2];//dp[i][0]表示放第i列时放满了，dp[i][1]表示放第i列时该列还有一个空格

signed main() {
int N; cin >> N;
dp[0][0] = 1; dp[1][0] = 1; dp[1][1] = 0;//初始，不存在是1种情况，单独1个是恒不存在的，第1列满只有一种
for (int i = 2; i <= N; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]) % 10000;//要么是长条横着放，留出1个空，要么是竖着放，放满，要么是L型的，可以向上向下两种放法
dp[i][1] = (dp[i - 2][0] + dp[i - 1][1]) % 10000;//一个L型横着搭一个长条，或者就是一个L型
//注意dp[i][1]实际上分为上凸出和下凸出，但是我们只需要算一个，另一个的计数是和这个相同的，在用到的时候*2就可以了
}
cout << dp[N][0] % 10000 << endl;
return 0;
}
`