14949 외계 미생물

DP로 풀었다.

날짜 : depth

현 세대 : x

다음 세대 : y

다른 코드들과 비교해보니 시간차이가 많이 난다. 나중에 다시 풀어봐야겠다.

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
 
typedef long long ll;
int h, w;
ll d[6][201][201], mod = 1000000007;
 
// 현 세대 x, 다음 세대 y마리
ll dp(int depth, int x, int y) {
    if (depth == h) {
        return y ? 0 : 1;
    }
    if (!x) {
        return y ? dp(depth + 1, y, 0) : 0;
    }
    if (d[depth][x][y] != -1) return d[depth][x][y];
    ll ans = 0;
    for (int i = 0; y + i <= w; i++) {
        ans += dp(depth, x - 1, y + i);
        ans %= mod;
    }
    d[depth][x][y] = ans%mod;
    return d[depth][x][y];
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d%d", &h, &w);
    if (!h) printf("1");
    else printf("%lld", dp(0, 1, 0)%mod);
 
    return 0;
}