동적 계획 단순화(HDU2041, HDU2044, HDU2045, HDU2046, HDU2047)

추이는 동태 기획의 핵심 사상이라고 할 수 있다. 다음은 항저우전기에서 비교적 간단한 추이 문제 몇 가지를 정리했다.
HDU2041 슈퍼 계단:
제목 대의: n계단이 있습니다. 당신은 1계단에 있습니다. 매번 한 걸음 또는 두 걸음만 올라갈 수 있습니다. n계단까지 올라갈 때 모두 몇 가지 다른 방법이 있는지 물어보세요.
쉽게 알 수 있는 M=2시 N=1, M=3시 N=2, M>3시에는 F[M]=F[M-1]+F[M-2]가 있다. 즉, M 단계 계단에 도달하는 방법은 M-1 단계 계단에 도달하는 수와 M-2 단계 계단에 도달하는 수를 더한 것이다.
실질은 바로 피보나치 수열인데 n의 범위가 비교적 작다는 것을 감안하여 표를 치면 된다.
 

#include 

#include 
using namespace std;
int ans[45];
void init()
{
    ans[2]=1;
    ans[3]=2;
    for(int i=4;i<42;i++)
      ans[i]=ans[i-1]+ans[i-2];
}
int main()
{
    init();
    int t,n;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        printf("%d
",ans[n]);
    }
    return 0;

}

HDU2044 작은 벌 1마리:
이 문제는 2041과 실질적으로 같다. a에서 b까지의 노선수를 1에서 b-a+1까지의 노선수로 보면 사실은 피보나치 수열이다.

#include 
#include 
using namespace std;
long long ans[55];
void init()
{
    ans[2]=1;
    ans[3]=2;
    for(int i=4;i<52;i++)
      ans[i]=ans[i-1]+ans[i-2];
}
int main()
{
    init();
    int t,a,b;
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&a,&b);
        cout<

 
HDU2045 쉽지 않은 제품군 (3) LELE의 RPG 당면 과제:
제목의 대의: 한 줄의 n개의 네모가 있는데 각 네모는 빨간색, 분홍색, 녹색 세 가지 색깔 중 하나로 칠한다. 두 개의 서로 인접한 네모가 동색일 수 없고 첫 번째 네모와 마지막 네모도 동색일 수 없다. 모두 몇 가지 다른 칠법이 있느냐고 묻는다.
i번째 칸에 대해 말하자면 그의 도장 방법 f(i)는 i-1개의 칸의 색깔과 첫 번째 칸의 색깔에 달려 있다. 만약에 i-1개의 칸의 색깔이 첫 번째 칸과 다른 색이라면 i번째 칸은 하나의 도장법만 있고 f(i)=1*f(i-1)가 있다.만약에 i-1개의 칸이 첫 번째 칸과 같은 색이라면 우리는 이 칸을 고려할 필요가 없다. 동시에 i개의 칸은 두 가지 다른 도장법이 있는데 f(i)=2*f(i-2)가 있다.덧셈 원리에서 우리는 점차적인 공식을 얻어냈다. f(n)=f(n-1)+2*f(n-2).f(1)=1, f(2)=f(3)=6을 초기화하면 되는데 f(3)에 대해서는 비교적 특수하다.

#include 
#include 
using namespace std;
int main()
{
    long long f[51];
    int n,i;
    f[1]=3;
    f[2]=6;
    f[3]=6;
    for(i=4;i<=50;i++)
      f[i]=f[i-1]+2*f[i-2];
    while(scanf("%d",&n)!=-1)
      cout<

HDU2046 골패점 격자:

#include 
#include 
using namespace std;
long long ans[55];
void init()
{
    ans[1]=1;
    ans[2]=2;
    for(int i=3;i<52;i++)
      ans[i]=ans[i-1]+ans[i-2];
}
int main()
{
    init();
    int n;
    while(scanf("%d",&n)!=-1)
      cout<

HDU2047 소의 EOF 쇠고기 꼬치:
다음 문자의 경우
(1)'O'라면 앞의 자모는'O'가 아닐 것이다. 방법수는 2곱하기 전 n-2개의 방법수, 즉 f(n)=2*f(n-2)와 같다.
(2)'O'가 아니면'E'와'F'두 가지 상황이 있는데 상위 n-1개의 방법수, 즉 f(n)=2*f(n-1)를 곱한다.
덧셈 원리: f(n)=2*(f(n-1)+f(n-2)).

#include 
#include 
using namespace std;
int main()
{
    long long f[41];
    int n,i;
    f[1]=3;
    f[2]=8;
    for(i=3;i<=40;i++)
      f[i]=2*(f[i-1]+f[i-2]);
    while(scanf("%d",&n)!=-1)
      cout<