검지offer-귀속과 순환

1. 피보나치 수열
해:
더 이상 할 말이 없다. 직접 효율적인 스크롤 교체 해법을 써라.행렬 해법과 특징 근해법은 여기서 토론하지 않겠습니다.

class Solution:
    def Fibonacci(self, n):
        # write code here
        if n <= 1:
            return n
        dp_0, dp_1 = 0, 1
        for i in range(2, n+1):
            dp_0, dp_1 = dp_1, dp_0 + dp_1
        return dp_1

　　
 
2. 계단 오르기
개구리 한 마리가 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있다.이 개구리가 n급의 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해라.
해:
이 문제는 사실 피보나치 수열이다.폭력의 귀속 이외의 해법을 써라.
귀속+기억화, 위에서 아래로.

class Solution:
    def jumpFloor(self, number):
        # write code here
        memo = [0] * (number + 1)
        def helper(n, memo):
            if n <= 2:
                memo[n] = n
                return memo[n]
            if memo[n] > 0:
                return memo[n]
            ans = helper(n-1, memo) + helper(n-2, memo)
            memo[n] = ans
            return memo[n]
        return helper(number, memo)

　　
동적 계획은 밑에서 위로 올라가고 상태 이동은 간단하며 1차원 그룹을 열 필요가 없다.

class Solution:
    def jumpFloor(self, number):
        # write code here
        if number <= 2:
            return number
        f1, f2 = 1, 2
        for i in range(3, number+1):
            res = f1 + f2
            f1 = f2
            f2 = res
        return res

　　
 
3. 변태가 계단을 뛰어오르다
개구리 한 마리가 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있고...그것도 n계단을 올라갈 수 있다.이 개구리가 n급의 계단을 뛰어오르는 데는 모두 몇 가지 방법이 있는지 구해라.
해:
f(n) = f(n-1) + f(n-2) + ... + f(n-(n-1)) + f(n-n).n = 1 시 한 가지 점프법만 있고, f(1) = 1;n = 2시에는 두 가지가 있습니다. f(2) = 2 = f(2-1) + f(2-2).분명히 f(n-1) = f(n-2) + f(n-3) +...+f(1)+f(0), 추이 공식은 f(n)= 2*f(n-1)이다.
차례로 실현되다

class Solution:
    def jumpFloorII(self, number):
        if number == 1:
            return 1
        return 2*self.jumpFloorII(number-1)

　　
f(n) = 2*f(n-1) = 2*2*f(n-2) = ... = 2n-1

class Solution:
    def jumpFloorII(self, number):
        # write code here
        return 2**(number-1)

 
　　
4. 직사각형 덮어쓰기
우리는 2*1의 작은 직사각형으로 가로나 세로로 더 큰 직사각형을 덮을 수 있다.실례지만 n개의 2*1의 작은 사각형으로 중첩 없이 2*n의 큰 사각형을 덮는 방법은 모두 몇 가지가 있습니까?
해:
f(1) = 1, f(2) = 2, f(n)일 때 두 가지 상황이 있는데 먼저 세로로 놓고 f(n-1)종이 있다.먼저 두 개의 가로를 놓은 다음에 f(n-2)종이 있기 때문에 역시 피보나치 수열이다.

class Solution:
    def rectCover(self, number):
        # write code here
        if number <= 2:
            return number 
        fn1 =2
        fn2 = 1
        for i in range(3, number+1):
            res = fn1 + fn2
            fn2 = fn1
            fn1 = res
        return res