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;
