走楼梯2(动态规划)

走楼梯2(动态规划)

// Problem: // Contest:// URL: Memory Limit: 1024 MB// Time Limit: 2000 ms// 2022-02-26 21:33:52// // Powered by CP Editor (namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);i++)#define per(i,l,r) for(int i=(l);i>=(r);i--)#define ll long long#define pii pair#define mset(s,t) memset(s,t,sizeof(t))#define mcpy(s,t) memcpy(s,t,sizeof(t))#define fi first#define se second#define pb push_back#define all(x) (x).begin(),(x).end()#define SZ(x) ((int)(x).size())#define mp make_pairconst ll mod = 1e9 + 7;inline ll qmi (ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans = ans * a%mod; a = a * a %mod; b >>= 1; } return ans;}inline int read () { int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch=='-'),ch= getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return f?-x:x;}template void print(T x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x/10); putchar(x % 10 + '0');}inline ll sub (ll a, ll b) { return ((a - b ) %mod + mod) %mod;}inline ll add (ll a, ll b) { return (a + b) %mod;}inline ll inv (ll a) { return qmi(a, mod - 2);}#define int long longvoid solve() { int n; cin >> n; int f[55][3]; memset(f, 0, sizeof f); f[0][0] = f[1][0] = 1; for (int i = 2; i <= n ;i ++) { f[i][0] = f[i - 1][1] + f[i - 1][2] + f[i - 1][0]; f[i][1] = f[i - 2][0]; f[i][2] = f[i - 2][1]; } int ans = 0; for (int i = 0; i <= 2; i ++) ans += f[n][i]; cout << ans << endl;}signed main () { solve(); return 0;}

f[i][j]表示走到第i阶并且已经走了j步跨两阶 启发：缺什么就补什么。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。