class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size() == 0)
            return true;

        vector<int> dp(nums.size(), 0);
        dp[0] = max(0, nums[0]); //steps we still have after the step 0
        for(int i = 1; i < nums.size(); i++){
            if(dp[i-1] < 0)
                return false;

            //steps we have after step i, we can either jump from prev-prev step
            //  or prev step
            dp[i] = max(dp[i-1], nums[i-1]) - 1;
        }

        return dp.back() >= 0; //need to have step available       
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;

        // dp contains the jump needed to reache current step
        vector<int> dp(nums.size(), INT_MAX);
        dp[0] = 0; //need 0 jump to reach step 1

        for(int i = 0; i < nums.size(); i++){
            //from step i, one is able to jump to step i + nums[i]
            int j = min(i + nums[i], (int)nums.size()-1);
            //update jump num in [i:j]
            for(; j >= i; j--){
                //if step j is already reachable in previous jump,
                //  the current jump cannot have less jump num, therefore break out
                if(dp[j] < INT_MAX){
                    break;
                }
                dp[j] = dp[i] + 1; //update jump num
            }
        }

        return dp.back();        
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
       vector<vector<int>> dp(m, vector<int>(n, 0));
       //only one path to reach the first col
       for(int i = 0; i < m; i++){
           dp[i][0] = 1;
        } 

        //only one path to reach the first row
        for(int j = 0; j < n; j++){
           dp[0][j] = 1;
        }

         //two path to reach the rest cell, from up and from left
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];        
    }
};

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid){
        int m = obstacleGrid.size();
        if (m == 0)
            return 0;
        int n = obstacleGrid[0].size();

        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++){
            if(obstacleGrid[i][0] == 1){
                break;
            }else{
                dp[i][0] = 1;
            }
        }

        for (int j = 0; j < n; j++){
            if(obstacleGrid[0][j] == 1){
                break;
            }else{
                dp[0][j] = 1;
            }
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else{
                    //cout << dp[i - 1][j] << " "<< dp[i][j - 1] << endl;
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    //dp.at(i).at(j) = dp.at(i-1).at(j) + dp.at(i).at(j-1);
                }
            }
        }

        return dp[m - 1][n - 1];        
    }    
};

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        if(row <= 0)
            return 0;
        int col = grid[0].size();

        vector<vector<int>> costs(row, vector<int>(col, 0));
        costs[0][0] = grid[0][0];
        //first column
        for(int i = 1; i < row; i++){
            costs[i][0] = grid[i][0] + costs[i-1][0];
        }

        //first row
        for(int j = 1; j < col; j++){
            costs[0][j] = grid[0][j] + costs[0][j-1];
        }

        //traversal the rest cells
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                costs[i][j] = grid[i][j] + min(costs[i-1][j], costs[i][j-1]);
            }
        }

        return costs[row-1][col-1];        
    }
};