DP problems, sequence problems, grids problem

 1. Longest Increasing Subsequence (LeetCode)

Given an unsorted array of integers, find the length of longest increasing subsequence. (Note: it can jump, skip....only condition is going up) For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

Solution :O(n^2) is easy to figure out. Create DP table from back.  Clearly, the last element only get length 1.  The one before it, if smaller, can get 2; otherwise 1.  The next one before it, can link to whichever later one which is bigger than him, and choose the biggest link. Two nested for loop should do everything. 

//O(n^2)  DP // -- ----- 10, 9, 2, 5, 3, 7, 101, 18 

    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size()==1) return 1;
        int global=1;
        vector<int>count(nums.size(),1);        
        for (int i=nums.size()-2;i>=0; --i){
            for (int j=i+1; j<nums.size(); ++j ){
                if (nums[j]>nums[i]){
                    count[i]=max(count[i],count[j]+1);
                }
                if (count[i]>global) global= count[i];
            }
        }
        return global;
    }


2. Edit distance (LeetCode)

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution:  This problem obviously falls in DP category.  Suppose we match "body" to "about". We can start with the end [bod]y ->[abou]t.  

1. If we know [bod]->[abou] best in X time operation,  since 'y' is different with 't', we need X+1;  if we know [body]->[abou] takes Y times, we insert a 't', take Y+1; if we know [bod]->[about] takes Z time, delete 'y', we take Z+1;  We look for min (X+1, Y+1, Z+1)

2. Suppose the last letter is the same, the previous three numbers change to  X, Y+1, Z+1.  We look for min(X,Y+1, Z+1);

3. do not forget to save each cell if we once calculated it.

4. Initialize with 0. That is suppose both word are empty, so we have determined value.   void to void takes 0; void to length 1 ,takes 1...., so row 0 filled with 0->N;  Column 0 filled with 0->M.

5 Before this line, we all assume we do upside down way. We can do bottom up first filling table[1][1], checking word1[0] ->word2[0].

    int act(string src, string dst, int m, int n){

        if (m==0) return n;
        if (n==0) return m;
    
        //(m,n) has three paths  (m-1,n), (m, n-1) (m-1,n-1)
        if (table[m][n]<INT_MAX) return table[m][n];
    
        if (table[m-1][n-1]==INT_MAX)
            {table[m-1][n-1]=act(src, dst, m-1, n-1);}
        if (table[m-1][n]==INT_MAX)  
            {table[m-1][n]=act(src, dst, m-1, n);}
        if (table[m][n-1]==INT_MAX)  
            {table[m][n-1]=act(src, dst, m, n-1);}
    
        if (src.at(m-1)==dst.at(n-1)) {
            return min(table[m-1][n-1], min(1+table[m-1][n], 1+table[m][n-1]));
        } else{
            return min(table[m-1][n-1]+1, min(1+table[m-1][n], 1+table[m][n-1]));
        }
    
    }

    vector<vector<int>> table;
    int minDistance(string src, string dst) {
            int M=src.length();
            int N=dst.length();
            if (M==0) return N;
            if (N==0) return M;
            table.resize(M+1, vector<int>(N+1, INT_MAX));
            table[0][0]=0;
            int counter=0;
            for (int &n:table[0]) n=counter++;
            for (int m=0; m<M+1; ++m ) table[m][0]=m;
            return act(src, dst, M, N);
    }


3. Extension of problem 2.  If we want every operation path is a valid word in a dictionary?  give the path or if no path through return empty path.

4.Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there?

Solution: typical DP problem. This number is actually Combine(m-1+n-1, m-1) = (m+n-2)!/ (m-1)!(n-1)!  
Easy?  Yes, but it is hard to avoid overflow  if you just return this one line.  DP is easier comparing to that.  
This gives a hind how to answer the combination problems too,  If the question is C(m,n), I would code in this way.  The equation holds for  C(m,n)= C(m-1,n)+C(m, n-1)
Also C(m,n)= C(m-1, n) (m+n)/m;    C(m,n)= C(m, n-1) (m+n)/n;  

class Solution {
public:
    vector<vector<int>> ct;
    int path(int m, int n, int y, int x){
        if (ct[y][x]) return ct[y][x];
        if (y==m-1 ||x==n-1) return 1; 
        ct[y][x] = path(m,n,y+1,x)+ path(m,n,y,x+1);
        return ct[y][x];
    }    
    int uniquePaths(int m, int n) {
        ct.resize(m, vector<int>(n,0));
        return path(m,n, 0,0);
    }

};

5. Unique Paths II

Follow up for "Unique Paths":   Now consider if some obstacles are added to the grids. How many unique paths would there be?An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example,There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2. Note: m and n will be at most 100.

Solution: My code is messy. Just try to set the boundary parameters. Actually for O complexity vise,  it does not need to set. But it just cannot pass leetecode time limits. So instead of only setting the corner, I have to set two boundary sides.

class Solution {
public:
    vector<vector<int>> ct;
    int m, n;
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        m=obstacleGrid.size();
        n= m==0? 0:obstacleGrid[0].size();
        ct.resize(m, vector<int>(n,-1));
        bool set0=false;
        for (int i=n-1; i>=0; --i){
            if (set0) {ct[m-1][i]=0; continue;}
            if (obstacleGrid[m-1][i]!=1) ct[m-1][i]=1;
            else {ct[m-1][i]=0; set0= true;}
        }
        for (int i=0; i<m; ++i) ct[i][n-1]=0;
        for (int i=m-1; i>=0; --i){
            if (obstacleGrid[i][n-1]!=1) ct[i][n-1]=1;
            else break;
        }
        return path(obstacleGrid, 0,0);
    }
    int path(vector<vector<int>>& obstacleGrid, int y, int x){
        if (obstacleGrid[y][x]==1) return 0;
        if (ct[y][x]!=-1) return ct[y][x];
        ct[y][x] = path(obstacleGrid,y+1,x)+ path(obstacleGrid,y,x+1);
        return ct[y][x];
    }

};