리트코드 70 계단오르기 c++ // 재귀함수 리턴값 전파 이해, dp

https://leetcode.com/problems/climbing-stairs/

1. 전체코드

int dp[45+4];
int N;

class Solution {
public:
    //해당 층에 올랐을때, 그때 경우의수
    int go(int cur){
        //cout<<cur<<" ";
        if(cur>N){
            return 0;
        }
        if(cur==N){
            return 1;
        }
        if(dp[cur]!=-1) return dp[cur];

        dp[cur]=0;
        dp[cur]+=go(cur+1);
        dp[cur]+=go(cur+2);

        return dp[cur];
    }
    int climbStairs(int n) {
        N=n;
        memset(dp,-1,sizeof(dp));

        return go(0);    
    }
};

 

2. 재귀함수 리턴값 전파 이해

1. 자료구조 시간에 배운 (L R 나) 로 후위 표현식 재귀 계산을 떠올려보자!

2. 1의 입장에서

좌측노드는 1이 리턴되었다 //dp[1]+=go(2) // dp[1]+=1

우측노드는 0이 리턴되었다.  //dp[1]+=go(3) // dp[1]+=0

3. 즉, dp[cur]은 해당 노드에서 리턴되는 값(좌+우)인 것이다!

좌측노드값+우측노드값을 더해서

return 문을만나면 그값을 상위노드(0)로 보내주는 것이다!

4. 0번노드의 입장에서

좌측노드에서 1값을 받았고

우측노드에서 1값을 받았다.

그 합들을 dp[0]에 더해주고

최종적으로 리턴하는 것이다!