C++ with explaination - the road from DP to Fibonacci


  • 0
    T

    My first approach is DP because this is an optimization problem. So if we have the maximum way at "n-1" steps then the optimal steps at "n" is:
    We step like the n times different before then with another step -> optimal way with n-1 steps
    We step (n-1) times different before then the last 2 steps by once -> optimal way with n-2 steps
    Then we have: max[n] = max[n-1] + max[n-2] -> turn out it is a Fibonacci! XD

    int climbStairs(int n) {
            if (n==0) return 0;
            if (n==1) return 1;
            if (n==2) return 2;
    
            int oldWay1 = 1;
            int oldWay2 = 2;
            int way;
            
            for (int i=3; i <=n; i++) {
                //DP[i] = DP[i-1] + DP[i-2];
                way = oldWay1 + oldWay2;
                oldWay1 = oldWay2;
                oldWay2 = way;
            }
            return way;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.