Ivan the Fool and the Probability Theory （思维DP）

题目

https://codeforces.com/contest/1248/problem/C

题意

给你一个n*m的方格，让你涂成黑白，问每个格子最多和一个临近格子相同的方案数

思路

推理发现如果某一行存在一个相邻的相同，那么他的下一行是固定的

只有一行的方案数很好求 dp[i] = dp[i-1] + dp[i-2]

这个相邻的可能在某一列也可能在某一行，ans = dp[n] + dp[m]

但黑白相间会计算两次 ans = ans - 2;

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 1e5+100;
const ll mod = 1e9+7;
ll dp[maxn];
int main()
{int n,m;scanf("%d%d",&n,&m);dp[1] = 2,dp[2] = 4;for(int i = 3;i <= max(n,m);i++){dp[i] = (dp[i-1] + dp[i-2]) % mod;}ll ans = (dp[n] + dp[m] - 2) % mod;printf("%lld\n",ans);return 0;
}