python 동적 기획 알고리즘 실례 상세

만약 여러분이 이 생소한 용어에 대해 이해하지 못한다면 먼저 편집본을 들어 여러분에게 현실 생활의 실제 사례를 들어보세요. 지금은 핸드폰이 상당히 편리하고 돈을 지불할 수 있지만 처음에 우리는 동전을 자주 사용했습니다. 그 중에서 우리가 손에 5마오나 1원짜리 동전이 많으면 어떻게 5원을 모을 수 있을까요?이런 과정을 동적 기획 알고리즘이라고도 할 수 있으니 다음은 상세한 내용을 살펴보자.
피보나치 수열에서 동적 계획을 보다
피보나치 수열: Fn = Fn-1 + Fn-2 (n = 1, 2 fib (1) = fib (2) = 1)
연습: 피보나치 수열의 n항을 풀기 위해 귀속과 비귀속 방법을 사용한다
코드는 다음과 같습니다.

# _*_coding:utf-8_*_
def fibnacci(n):
  if n == 1 or n == 2:
    return 1
  else:
    return fibnacci(n - 1) + fibnacci(n - 2)
 print(fibnacci(10)) # 55

위의 애매모호한 설명을 이해하지 못하면 다음과 같은 직관적인 코드가 있다.

f(1) = 1
f(2) = 1
f(3) = f(1) + f(2) = 1+ 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3
...
f(n) = f(n-1) + f(n-2)

인스턴스 확장:
계단을 오르다
만약 네가 계단을 오르고 있다면, n계단이 있어야만 옥상에 도착할 수 있다
매번 너는 한두 개의 계단을 올라갈 수 있다.너는 몇 가지 다른 방법으로 옥상까지 올라갈 수 있니?
주의: 주어진 n은 정수입니다.
예:
예 1:
입력: 2
출력: 2
설명: 옥상까지 올라갈 수 있는 두 가지 방법이 있다.
1.1 단계 + 1 단계
2.2 단계
예 2:
입력: 3
출력: 3
설명: 옥상까지 올라갈 수 있는 세 가지 방법이 있다.
1.1 단계 + 1 단계 + 1 단계
2.1 단계 + 2 단계
3.2 단계 + 1 단계
확인:
만약 두 가지 예시를 특별히 잘 보지 못한다면 당신은 계단을 0으로 할 수 있다. 그러면 계단을 오르는 방법은 0가지가 필연이다. 계단이 1이면 계단을 오르는 방법은 1가지밖에 없다.
4 계단:
입력: 4
출력: 4
1.1 단계 + 1 단계 + 1 단계 + 1 단계
2.2 단계 + 2 단계
3.1 단계 + 2 단계 + 1 단계
4.2 단계 + 1 단계 + 1 단계
5.1 단계 + 1 단계 + 2 단계
그럼
계단수 계단 오르기 방법
0 0
1 1
2 2
3 3
4 5
...
잘 안 보일 것 같으면 5 단계, 6 단계를 추리해 보시면...
n계단을 오르고 싶을 때 p(n-1)+p(n-2)p를 계단을 오르는 방법으로 얻을 수 있다

class Solution:
  def climbStairs(self, n: int) -> int:
    num_list = [0,1,2]
    if n==1:
      return num_list[1]
    elif n==2:
      return num_list[2]
    else:
      for i in range(3,n+1):
        num_list.append(num_list[i-1]+num_list[i-2])
    print(num_list)
    return num_list[n]

obj = Solution()
result = obj.climbStairs(10)
print(result)

리코드를 제출한 사람은 12.72% 에 불과했다.최적화를 통해

class Solution:
  def climbStairs(self, n: int) -> int:
    a,b,c = 0,1,2
    if n == 1:
      return b
    if n == 2:
      return c
    while n>0:
      c = a + b
      a,b = b,c
      n -= 1
    return c
obj = Solution()
result = obj.climbStairs(8)

이쯤에서python 동적 기획 알고리즘의 실례에 대한 상세한 설명을 드리겠습니다. 더 많은python 동적 기획 알고리즘이 어떤 내용인지 저희 이전의 글을 검색하거나 아래의 관련 글을 계속 훑어보십시오. 앞으로 많은 응원 부탁드립니다!