[openjudge] 네모 밟기.

1397 단어 dp문제풀이
묘사
사각형 행렬이 하나 있는데, 행렬의 경계는 무한히 먼 곳에 있다.우리는 다음과 같은 가설을 한다. a. 한 걸음 한 걸음 걸을 때마다 현재의 격자에서 한 칸만 이동하고 특정한 인접한 격자까지 걸어갈 수 있다.b. 지나간 칸이 바로 내려앉아 두 번 다시 걸을 수 없다.c. 북쪽, 동쪽, 서쪽 세 방향으로만 갈 수 있다.실례합니다: 만약 격자 행렬에서 n보를 걷는 것을 허락한다면 모두 몇 가지 다른 방안이 있습니까?두 가지 주법은 한 걸음만 다르면 다른 방안으로 여겨진다.네모난 칸에서 걷는 걸음걸이 n (n < = 20) 을 입력하여 계산된 방안의 수량 예시 입력
2
샘플 출력
7

【코드】
#include
#include
#include
int f[50];
int main(){
    int n;
    scanf("%d",&n);
    f[0]=1; f[1]=3;
    for (int i=2;i<=n;i++){
        int sum=0;
        for (int j=0;j<=i-2;j++)
            sum =sum + f[j];
        f[i] = f[i-1] + 2*(sum +1 );

    }
    printf("%d
",f[n]); }

from       http://www.cnblogs.com/easyFancy/archive/2013/04/05/3000759.html
또 다른 사고방식, orzzyx
남쪽, 서쪽, 동쪽에서 걸어오는 길이 얼마나 되는지, 되돌아갈 수 없기 때문에 동쪽과 서쪽에서 걸어오는 길은 두 가지 가능성만 있을 뿐, 남쪽에서 걸어오는 길은 세 가지 가능성이 있다. 그리고 매번 갱신된다.
이런 사고방식 은 점진적 이라고 할 수 는 없고, 약간 모의 적 인 의미 가 있다
【코드】
#include
#include
#include
using namespace std;
int n,s,w,e;
int f[200];
int main(){
	scanf("%d",&n);
	f[1]=3;
	s=w=e=1;
	for (int i=2;i<=n;++i){
		int t;
		f[i]=s*3+w*2+e*2; 
		t=s+w+e,w=s+w,e=s+e,s=t;
	}
	printf("%d",f[n]);
}

좋은 웹페이지 즐겨찾기