9.5 cc dp-rotate now

9.1] Climbing Stairs

    int climbStairs(int n) {
        if (n<0) return 0;
    
        queue<int> q ({1, 1});
        for (int i=2; i<=n; ++i) {
            q.push(q.front()+q.back());
            q.pop();
        }
        return q.back();
    }

LIC

• dp O(n^2)
  lenLIS[i] = max (lenLIS[j] + 1), where nums[j]<nums[i] and j<i and i>0

• improved w/ binary search O(nlogn)
  // vector<int> LIS(n, -1); // stores the actual LIS, initialize [0] to be 1
  // int lasti = 0; // end pointer points to last char of LIS
  // LIS[lasti] = nums[0];

    // for (int curr=1; curr<n; ++curr) {
    //     if (LIS[lasti] < nums[curr]) {
    //         LIS[++lasti] = nums[curr];
    //     } else {
    //         //binary search to find a pos to push: s.t. leftmost pos that nums[pos] > nums[curr]
    //         int low = 0, high = lasti, mid = -1;
    //         while (low<high) {
    //             mid = low + (high-low)/2;
    //             if (LIS[mid] < nums[curr]) {
    //                 low = mid+1;
    //             } else {
    //                 high = mid;
    //             }
    //         }
    //         LIS[low] = nums[curr];
    //     }
    // } // end for
    // return lasti+1;