하락장도 상승장도 아니다.

대신 하향식이며 상향식이다.

여름이었다.

하향식 분석

큰 문제를 작은 문제로 쪼개는 방식이다.
재귀 함수 자체가 대표적 하향식이다.

문제를 풀기위해 작게 쪼개고

• 그 작은 걸 풀기위해 더 작게 쪼개고
  
  • 더 작은 걸 풀기위해 더더 작게 쪼개고
    
    • 더더 작은 걸 풀기위해 더더더 작게 쪼개고
      
      • 더더더 작은 걸 풀기위해 더더더더 작게 쪼개고
        
        • 더더더더 작은 걸 풀기위해 더더더더더 작게 쪼개고
          
          • 이하 생략

이런 식이다.

피보나치 수열의 예시다.

def fib(n):
    if n <= 2:
        return 1
    return fib(n-1) + fib(n-2)

fib(n)을 fib(n-1), fib(n-2)이라는 더 작은 걸로 쪼갠다.

상향식 분석

슬프게도 상향식 분석을 한다고 불장이 되지는 않는다.

대신 작은 문제를 쌓아 올려 큰 문제까지 해결 가능하다.

보통은 반복문을 써서 차근히 올라간다.

먼치킨물이 판치는 요즘에 어울리지 않는 왕도물이다.

얘도 피보나치 수열로 예시 가능하다. ```py def fib(n): dp = [0, 1, 1] # 0, 1, 2번째 피보나치 값을 미리 저장 (dp[1]=1, dp[2]=1)

for i in range(3, n+1):
    dp.append(dp[i-1] + dp[i-2])
# 이전 2개의 값을 더해서 새로운 값을 계산

return dp[n]
# n번째 피보나치 수를 리턴 ``` <br>

흐름 : ```py i=3: dp[3]=dp[2]+dp[1]=1+1=2

i=4: dp[4]=dp[3]+dp[2]=2+1=3

i=5: dp[5]=dp[4]+dp[3]=3+2=5

i=6: dp[6]=dp[5]+dp[4]=5+3=8 ```

작은 값부터 미리 계산 후, 마지막에 원하는 값을 들고 온다.