279. Perfect Squares

Example: for n = 4
1st round:
    i = 1, j = 1: dp = [1]
2nd round:
    i = 2, j = 1: dp = [1 2]
3rd round:
    i = 3, j = 1: dp = [1 2 3]
4th round:
    i = 4, j = 1: dp = [1 2 3 4]
    i = 4, j = 2: dp = [1 2 3 1]

From the example above, let dp[i] be the least number of perfect squares for number i. So, for 1 <= j <= sqrt(i), we have dp[i] = min(dp[i], dp[i-j*j]+1).

1:  class Solution {  
2:  public:  
3:    int numSquares(int n) {  
4:      vector<int> dp(n+1, INT_MAX);  
5:      dp[0] = 0;  
6:      for (int i = 1; i <= n; i++) {  
7:        for (int j = 1; j*j <= i; j++) {  
8:          dp[i] = min(dp[i], dp[i-j*j]+1);  
9:        }  
10:      }  
11:      return dp[n];  
12:    }  
13:  };  

300. Longest Increasing Subsequence

Let dp[i] be the longest increasing subsequence till i. We need to move pointer from 1 to n-1 and for element i, we need to check from 0 to i-1, dp[i] = dp[j] + 1 if nums[i] > nums[j] and dp[j]+1 > dp[i].

1:  class Solution {  
2:  public:  
3:    int lengthOfLIS(vector<int>& nums) {  
4:      vector<int> dp(nums.size(), 1);  
5:      int maxLen = 0;  
6:      for (int i = 1; i < nums.size(); i++) {  
7:        for (int j = 0; j < i; j++) {  
8:          if (nums[j] < nums[i] && dp[i] < dp[j]+1) {  
9:            dp[i] = dp[j] + 1;  
10:          }  
11:        }  
12:      }  
13:      for (int i = 0; i < nums.size(); i++) {  
14:        maxLen = max(maxLen, dp[i]);  
15:      }  
16:      return maxLen;  
17:    }  
18:  };  

When I revisited this problem, the greedy algorithm seems working too. The idea is to keep an LIS vector, when the new number comes in, check it against the LIS, and replace the first number in LIS that is larger than the new number if any. Therefore the LIS always keeps the smallest increasing sequence and thus reaches the largest possibility to grow. With this algorithm, the searching can be modified to binary search in this algorithm so it can be improved to nlogn even faster than the DP.

1:  class Solution {  
2:  public:  
3:    int lengthOfLIS(vector<int>& nums) {  
4:      vector<int> lis;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        if (lis.empty() || nums[i] > lis[lis.size()-1]) lis.push_back(nums[i]);  
7:        else if (nums[i] > lis[0] || nums[i] < lis[lis.size()-1]) {  
8:          int j = 0;  
9:          while (nums[i] > lis[j]) j++;  
10:          lis[j] = nums[i];  
11:        }  
12:      }  
13:      return lis.size();  
14:    }  
15:  };  

304. Range Sum Query 2D - Immutable

Suppose we have a matrix dp[i][j] records the sum of rectangle of (0, 0, i, j). Then the sum of rectangle of (row1, col1, row2, col2) can be calculated by four rectangles: (0, 0, row2, col2), (0, 0, row1-1, col2), (0, 0, row2, col1-1), (0, 0, row1-1, col2-1). If you overlap these four rectangles, you'll find that:
(row1, col1, row2, col2) = (0, 0, row2, col2) - (0, 0, row1-1, col2) - (0, 0, row2, col1-1) + (0, 0, row1-1, col2-1)

1:  class NumMatrix {  
2:  private:  
3:    vector<vector<int>> sumMatrix;  
4:  public:  
5:    NumMatrix(vector<vector<int>> &matrix) {  
6:      if (matrix.size() > 0 && matrix[0].size() > 0) {  
7:        int rows = matrix.size();  
8:        int cols = matrix[0].size();  
9:        vector<vector<int>> dp(rows+1, vector<int>(cols+1, 0));  
10:        for (int i = 1; i <= rows; i++) {  
11:          int rowSum = 0;  
12:          for (int j = 1; j <= cols; j++) {  
13:            rowSum += matrix[i-1][j-1];  
14:            dp[i][j] = rowSum + dp[i-1][j];  
15:          }  
16:        }  
17:        sumMatrix = dp;  
18:      }  
19:    }  
20:    int sumRegion(int row1, int col1, int row2, int col2) {  
21:      return sumMatrix[row2+1][col2+1] - sumMatrix[row2+1][col1] - sumMatrix[row1][col2+1] + sumMatrix[row1][col1];  
22:    }  
23:  };  
24:  // Your NumMatrix object will be instantiated and called as such:  
25:  // NumMatrix numMatrix(matrix);  
26:  // numMatrix.sumRegion(0, 1, 2, 3);  
27:  // numMatrix.sumRegion(1, 2, 3, 4);  

309. Best Time to Buy and Sell Stock with Cooldown

We need to keep the profit of buying stock and the profit of selling stock.
When we buy stock, our profit will be subtracted by the price. When we sell stock, our profit will be added by the price. So we have following equations on day i:
For profit of buying stock, we have:
case 1: we sell stock on day i-2, and buy on day i;
case 2: we keeps the stock from day i-1 and do nothing on day i;
profitHasStock = max(profitNoStock[i-2]-prices[i], profitHasStock[i-1]);

For profit of selling stock, we have:
case 1: we have no stock on day i-1 and still do nothing on day i;
case 2: we have stock on day i-1, and sell stock on day i;
profitNoStock[i] = max(profitNoStock[i-1], profitHasStock[i-1]+prices[i]);

1:  class Solution {  
2:  public:  
3:    int maxProfit(vector<int>& prices) {  
4:      int n = prices.size();  
5:      if (n == 0 || n == 1) return 0;  
6:      // profitHasStock[i] indicates maximum profit with stock at hand on day i;  
7:      // note, the profit can be negative with stock at hand.  
8:      vector<int> profitHasStock(n, 0);  
9:      // profitNoStock[i] indicates maximum profit with no stock at hand on day i;  
10:      // obviously, we must sell all stocks on day n, so profitNoStock[n] will be the result.  
11:      vector<int> profitNoStock(n, 0);  
12:      profitHasStock[0] -= prices[0];  
13:      profitNoStock[1] = max(profitHasStock[0]+prices[1], profitNoStock[0]);  
14:      profitHasStock[1] = max(profitHasStock[0], profitNoStock[0]-prices[1]);  
15:      for (int i = 2; i < prices.size(); i++) {  
16:        profitHasStock[i] = max(profitNoStock[i-2]-prices[i], profitHasStock[i-1]);  
17:        profitNoStock[i] = max(profitNoStock[i-1], profitHasStock[i-1]+prices[i]);  
18:      }  
19:      return profitNoStock[n-1];  
20:    }  
21:  };  

312. Burst Balloons

This is a similar problem to matrix chain multiplication. This can be solved by divide-and-conquer with memorization. The basic idea behind is:

Let dp[i][j] to record the maximum sum for interval nums[i, j]. So for subinterval nums[start, end], if we need to pop out nums[k] in nums[start, end], the maximum sum for poping out nums[k] is dp[start][i-1] + nums[k]*nums[start-1]*nums[end+1]+dp[i+1][end]. Note nums[k] is the last element that need to pop out from nums[start, end], so the product should be nums[k]*nums[start-1]*nums[end+1]. dp[i][j] can be calculated recursively.

1:  class Solution {  
2:  public:  
3:    int maxCoins(vector<int>& nums) {  
4:      // let nums to have nums[-1] = nums[n] = 1  
5:      nums.insert(nums.begin(), 1);  
6:      nums.push_back(1);  
7:      vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), INT_MIN));  
8:      return helper(dp, nums, 0, nums.size()-1);  
9:    }  
10:    // note start "s" and end "e" constructs an exclusive interval (s, e)  
11:    int helper(vector<vector<int>> &dp, vector<int> &nums, int s, int e) {  
12:      if (dp[s][e] != INT_MIN) return dp[s][e];  
13:      if (e - s == 1) { dp[s][e] = 0; return 0; }  
14:      int res = 0;  
15:      for (int i = s + 1; i < e; i++) {  
16:        res = max(res, helper(dp, nums, s, i) + helper(dp, nums, i, e) + nums[i]*nums[s]*nums[e]);  
17:      }  
18:      dp[s][e] = res;  
19:      return res;  
20:    }  
21:  };  

321. Create Maximum Number

We need to compute the maximum number of length i from vector one and the maximum number of length k-i from vector two and then merge them together. After enumerating all possible i's, we'll get the maximum number. Therefore, there are two steps to achieve the goal:

1. create maximum number of lengths varying from 0 - k per input vector. This can be done dynamically. For example, for [9, 1, 2, 5, 8, 3], with length  = 5, we remove 1 and get [9, 2, 5, 8, 3]. When computing maximum number of length 4, we don't have to restart computing from the original input. Instead, given maximum number of length 5, we can compute maximum number of length 4 on top of it, i.e. remove 2 and get [9, 5, 8, 3].

2. merge the two maximum numbers. It's similar to merge linked list but with exception. When there are identical numbers in the two maximum numbers, we should move the pointer in the maximum number that hasn't reached the end or has larger digit in the end.

When I revisited this problem, I made mistake in
Line 28: I didn’t carefully think of the case where two numbers are equal. I should move i only when there is no more numbers after equal sequence or the first number after equal sequence in list1 is larger than that in list2.
Line 38: I moved the if-else clause into the while loop.

However, with following solution, I still got TLE. The problem is in line 8-13. Since list1 and list2 contains lists of size from 0 to k and we only care about the merged list of size k, so we only need to check pairs in list1 and list2 that can be merged to size k. Instead of traversing all pairs in list1 and list2, we only need to check pairs of nums of size i in list1 and nums of size k-i in list2.

1:  class Solution {  
2:  public:  
3:    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {  
4:      vector<vector<int>> dp1(k+1), dp2(k+1);  
5:      vector<int> res(k), tmp_result(k);  
6:      genDP(nums1, dp1, k);  
7:      genDP(nums2, dp2, k);  
8:      for (int i = 0; i <= k; i++) {  
9:        if (dp1[i].size() + dp2[k-i].size() < k) continue;  
10:        merge(dp1[i], dp2[k-i], tmp_result);  
11:        if (compare(tmp_result, res)) res = tmp_result;  
12:      }  
13:      return res;  
14:    }  
15:  private:  
16:    void genDP(vector<int>& nums, vector<vector<int>> &dp, int k) {  
17:      int start, i = 0;  
18:      for (start = 0; nums.size() > 0; start = (i == 0 ? 0 : i-1)) {  
19:        if (nums.size() <= k) {  
20:          dp[nums.size()] = nums;  
21:        }  
22:        for (i = start; i+1 < nums.size() && nums[i] >= nums[i+1]; i++);  
23:        nums.erase(nums.begin() + i);  
24:      }  
25:    }  
26:    void merge(vector<int> &nums1, vector<int> &nums2, vector<int> &res) {  
27:      int i = 0, j = 0, k = 0;  
28:      int ii = 0, jj = 0;  
29:      for (; i < nums1.size() && j < nums2.size(); k++) {  
30:        for (ii = i, jj = j; ii < nums1.size() && jj < nums2.size() && nums1[ii] == nums2[jj]; ii++, jj++);  
31:        if (jj == nums2.size() || ii < nums1.size() && nums1[ii] > nums2[jj]) {  
32:          res[k] = nums1[i];  
33:          i++;  
34:        } else {  
35:          res[k] = nums2[j];  
36:          j++;  
37:        }  
38:      }  
39:      while (i < nums1.size()) {  
40:        res[k++] = nums1[i++];  
41:      }  
42:      while (j < nums2.size()) {  
43:        res[k++] = nums2[j++];  
44:      }  
45:    }  
46:    int compare(vector<int> &nums1, vector<int> &nums2) {  
47:      int i = 0;  
48:      for (;i < nums1.size() && nums1[i] == nums2[i]; i++);  
49:      if (nums1[i] > nums2[i]) return 1;  
50:      else return 0;  
51:    }
52:  };  

First Meeting with Postgres

I had to uninstall Postgres as I forgot the password for default admin user "postgres". What stupid I am. It really makes things difficult. So I have to uninstall the postgres. OK, another bad thing I made is I installed postgres by EnterpriseDB installer. It's always not an easy way to uninstall stuff that was not installed by homebrew. Fortunately, I found the following way to uninstall the postgres:
http://stackoverflow.com/questions/8037729/completely-uninstall-postgresql-9-0-4-from-mac-osx-lion

After the uninstallation, I installed postgres by homebrew:
$brew update
$brew install postgres

OK, now I've installed postgres successfully. It's time to lauch the postgres server by:
$pg_ctl -D /usr/local/var/postgres -l /usr/local/var/postgres/server.log start
and check it is running:

$ps aux | grep postgres

Everything works as expected, and I tried to run rails but got an error:

FATAL:  role "dashboard" does not exist

It seems that I don't have that role created in postgres. Not a problem, it's easy to create a role by:

$createuser -P dashboard

Log into postgres and check the role:

$psql -d postgres -U [login user name]

postgres=# SELECT rolname FROM pg_roles;

       rolname       

---------------------

... 

dashboard

Good! The role "dashboard" has been created successfully. Now try rails again. What? another error again?
PG::InsufficientPrivilege: ERROR:  permission denied to create database
Looks like the role "dashboard" doesn't have the permission to create database. Check the permission for "dashboard" in postgres:
postgres=# \du
                                 List of roles
     Role name      |                   Attributes                   | Member of
---------------------+------------------------------------------------+----------
dashboard |                                                | {}

Yeah, no permission at all for "dashboard". Grant it appropriate permission:
postgres=# ALTER ROLE dashboard CREATEROLE CREATEDB;

Now, run the rails again. Sigh...another error again:
"dashboard_development" does not exist

I see. It's most likely because I didn't do db:create and db:migrate. So, let me do it:

$bundle exec rake db:create db:migrate

Well, finally the website is up and running!