UVA11069 - A Graph Problem(DP)

UVA11069 - A Graph Problem(DP)
제목 링크
제목 대의: n점 드릴게요.너는 몇 개의 자열이 요구에 부합되는지 찾아내야 한다.우선 연속적인 숫자가 없고, 그 다음에 그 안에 무엇이든 넣을 수 없으며, 제1조의 요구를 위반하지 않는다.
문제풀이 사고방식: 모든 숫자를 발견하고 선정한 후에.앞으로 두 가지 선택이 있을 수 있다.그래서 f(n)=f(n+2)+f(n+3);경계: 숫자를 아래로 넣을 수 없을 때 1로 돌아갑니다.
코드:

#include <cstdio>
#include <cstring>

const int maxn = 100;

int n;
int dp[maxn];

void init () {

    memset (dp, 0, sizeof (dp));
}

int solve (int k) {

    if (k + 2 > n)
        return dp[k] = 1;
    if (dp[k])
        return dp[k];

    int &ans = dp[k];
    if (k + 2 <= n)
        ans += solve(k + 2);
    if (k + 3 <= n)
        ans += solve(k + 3);
    return ans;
}

int main () {

    while (scanf ("%d", &n) != EOF) {

        init();
        int ans = solve(1);
        if (n > 1)
            ans += solve(2);
        printf ("%d
", ans);                
    }
    return 0;
}