동적 계획 문제 (2) - 계단 뛰 어 내리 기

1761 단어 귀착 하 다이루어지다동적 계획계단 을 뛰어넘다추산 규칙
동적 계획 문제 (2) - 계단 뛰 어 내리 기
    
1. 제목 설명
한 계단 은 모두 n 계단 으로 한 번 에 1 계단 을 뛸 수도 있 고 2 계단 을 뛸 수도 있다.총 몇 개의 총 점프 법 이 있 는 지 를 구하 고 알고리즘 의 시간 복잡 도 를 분석한다.
2. 귀속 방식
    이 동태 계획 문제 에 대해 우 리 는 똑 같이 두 단계 로 나 누 어 생각한다.
4. 567917. 만약 에 우리 가 1 급 을 뛰 었 다 면 나머지 점프 법 은 f (n - 1) 이다
4. 567917. 만약 에 우리 가 2 급 을 뛰 었 다 면 나머지 점프 방법 은 f (n - 2) 이다
이 럴 때 우 리 는 다시 실현 할 수 있다, 천천히!우 리 는 재 귀적 인 조건 에서 벗 어 나 야 한다. 이것 도 없어 서 는 안 된다!
이 문제 에 있어 서 재 귀 조건 은 n = 1, 2 일 때 우 리 는 1, 2 로 돌아 가 는 것 이다.
왜 하나, 둘 이 죠?n = 1 일 때 한 가지 점프 방법 만 있 기 때문이다.n = 2 시 에는 두 가지 점프 법 이 있다.그리고 초기 값 이 생 겼 습 니 다. 그리고 두 가지 상황 만 있 습 니 다. (1 급 을 뛰 거나 2 급 을 뛰 거나) 이것 이 바로 피 보 나치 수열 문제 입 니 다!
코드 는 다음 과 같 습 니 다:
#include<iostream>
using namespace std; 

int findSolution(int N)
{
	int result[3]={0, 1, 2};   //    
	
	if(N<=2)
		return result[N]; 

	return findSolution(N-1)+findSolution(N-2);   //    
}

int main()
{
	int N=20; 

	int num=findSolution(N); 

	cout<<num<<endl;

	return 0; 
}

3. 비 귀속 방식
    비 귀속 방식 도 반드시 파악 해 야 한다!
    이것 이 피 보 나치 수열 문제 라면 비 귀속 방식 의 실현 도 비교적 쉽다 ~
    다음 과 같다.
#include<iostream>
using namespace std; 

int findSolution(int N)
{
	int Fab[3]={1,1}; 
	if(N<2)
		return 1; 

	for(int i=2; i<=N; i++)
	{
		Fab[2]=Fab[0]+Fab[1];   //          
		Fab[0]=Fab[1]; 
		Fab[1]=Fab[2]; 
	}
	return Fab[2]; 
}

int main()
{
	int N=20; 

	int num=findSolution(N); 

	cout<<num<<endl;

	return 0; 
}

    지적 해 야 할 것 은 이 문제 의 비 재 귀 방식 의 추산 규칙 이 비교적 비슷 하 다 는 것 이다. 그 당시 에 편 에서 보고 싶 지 않 았 기 때문에 여러분 들 은 앞으로 서로 다른 문제 의 추산 규칙 에 주의해 야 한다!
    또한 3 단 계 를 뛰 어 넘 을 수 있다 면 실현 하 는 사고방식 은 같 습 니 다. 초기의 몇 개의 값 만 바 꾸 면 됩 니 다 ~
[LeetCode] IP 주소 복원, 문제 풀이 보고서
<2012 11 2> U-boot(2) U-boot 구조 분석 및 이식 중점

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage