귀속과 동태 기획의 초보적 이해

먼저 피보나치 수열을 통해 두 개념의 피보나치 수열을 끌어낸다. 이미 알고 있는 f(0)=0, f(1)=1, f(n)=f(n-1)+f(n+2)는 각각 두 가지 다른 사상으로 f(n)를 구한다.

1. 반복:

귀속 문제를 해결하려면 먼저 함수 정의를 명확히 한 다음에 귀속 종지 조건을 찾아야 한다. 마지막으로 귀속 자식, 즉 귀속 과정을 정확하게 쓸 수 있어야 한다.

def F(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return F(n-1) + F(n-2)

그러나 상기 귀속 코드 중 많은 것이 중복 계산될 수 있기 때문에 개선하기 위해 이미 계산한 결과를 저장할 수 있기 때문에 기억화 검색을 이끌어낼 수 있다.

2. 기억 검색:

암호화된 검색을 코드로 수행한 결과는 다음과 같습니다.

mery = [-1]*(n+1)
def new_f(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if mery[n] == -1:
        mery[n] = new_f(n-1) + new_f(n-2)
    return mery[n]

3. 동적 계획:

피보나치 수열이 동적 기획의 사상으로 해결되면 코드는 다음과 같다.

def dp(n):
    mery = [-1]*(n+1)
    for i in range(0, n+1):
        if i == 0:
            mery[i] = 0
        elif i == 1:
            mery[i] = 1
        else:
            mery[i] = mery[i-1] + mery[i-2]
    return mery[n]

4. 동규와 귀속의 총결:

이때 두 가지 방법을 자세히 살펴보면 피보나치 수열 문제를 예로 들면 f(n)와 전 두 가지가 관련이 있다는 것을 발견했다. 귀속하는 방법은 f(n)부터 시작하여 전 항목을 끊임없이 구하고 귀속 중지 조건을 만족시킬 때까지 한다.다시 동태적인 계획을 보면 f(n)가 앞의 두 항목과 관련이 있다는 것을 알 수 있다. 규칙을 움직이는 방법은 첫 번째 항목부터 n번째 항목까지 구하는 것이다.양자의 주요 차이점: 양자의 가장 큰 차이점은 문제를 사고하는 방식이 다르다는 것이다. 귀속은 위에서 아래로의 사고 방식이고 귀속은 아래에서 아래로의 사고 방식이다.귀속 층수가 너무 깊으면 창고가 넘치는 문제가 생기기 쉽다.

5. 실전 문제 분석:

개구리 변태가 계단을 뛰어넘는 문제를 예로 들면 개구리 한 마리가 한 번에 1계단을 뛸 수도 있고 2계단을 뛸 수도 있다. 이것은 n계단을 뛸 수도 있다.이 개구리가 n급 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해 보세요.(제목은 우객망에서 유래한 것) 우선 귀속 방법을 본다.

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        mery = [-1]*(number+1)
         
        def dp(n):
            if n == 1 or n == 0:
                return 1# 
            if mery[n]==-1:
                tmp = 0
                for i in range(1,n+1):
                    tmp += dp(n-i)
                mery[n] = tmp
            return mery[n]
        return dp(number)

다시 한 번 규칙을 살펴보자.

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, n):
        # write code here
        dp = [0]*(n+1)
        dp[0] = 1
         
        for i in range(1,n+1):
            tmp = 0
            for j in range(0,i):
                tmp += dp[j]
            dp[i] = tmp
        return dp[n]