dp相关算法题

class  {
    public int rob(int[] nums) {
        if(nums.length == 0)return 0;
        if(nums.length == 1)return nums[0];
        if(nums.length == 2)return Math.max(nums[0],nums[1]);
        int[] dp = new int [nums.length + 1];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        int res = dp[1];
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

//todo
package leleyi.study.algorithms.dp;

public class HouseRObber2 {
    public int rob(int[] nums){
        if (nums.length == 0) return 0;
        if (nums.length == 1) return Math.max(nums[0], nums[1]);
        int temp0, temp1, cur0 = 0, cur1 = 0, pre0 = 0, pre1 = 0;
        for (int i = 0; i < nums.length - 1; i++){
            //begin at 0
            temp0 = pre0;
            pre0 = cur0;
            cur0 = Math.max(temp0 + nums[i], cur0);
			//begin at 1
            temp1 = pre1;
            pre1 = cur1;
            cur1 = Math.max(temp1 + nums[i + 1], cur1);
        }
        return Math.max(cur0, cur1);
    }
}

// dp[i] = cost[i] + min(dp[i - 1], d[i - 2])
class  {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i < cost.length ; i++){
            dp[i] = cost[i] + Math.min(dp[i - 1], dp[i-2]);
        }
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }
}

// dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
// dp[j] = dp[j - 1] + dp[j];
class  {
    public int uniquePaths(int m, int n) {
//         int dp[][] = new int[m + 1][n + 1];
//         for(int i = 0; i < m; i++){
//             dp[i][0] = 1;
//         }
//         for(int j = 0; j < n; j++){
//             dp[0][j] = 1;
//         }
//         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];
//     }
        int dp[] = new int[n + 1];
        for(int i = 0; i < n; i++){
            dp[i] = 1;
        }
        for(int i = 1; i < m; i++){
            
            for(int j = 1; j < n; j++){
                dp[j] = dp[j - 1] + dp[j];
            }
        }
        return dp[n - 1];
    }
}

class  {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
       int m = obstacleGrid.length;
       int n = obstacleGrid[0].length;
       int dp[] = new int[n + 1];
       if(obstacleGrid[m-1][n-1] == 1) return 0;
       for(int i = 0; i < n; i++){
           if(obstacleGrid[0][i] == 1){
               dp[i] = 0;
               break;
           }else{
               dp[i] = 1;
           }
       }
       for(int i = 1; i < m; i++){
           if(obstacleGrid[i][0] == 1){
               dp[0] = 0;
           }
           for(int j = 1; j < n; j++){
               if(obstacleGrid[i][j] == 1){
                   dp[j] = 0;
               }
               else{
                   dp[j] = dp[j - 1] + dp[j];
               }
           }
       }
       return dp[n - 1];
    }
}

// d[i][j] = min(d[i - 1][j], d[i][j - 1]) + grid[i][j]
class  {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int [grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < grid[0].length; i++){
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
         for(int i = 1; i < grid.length; i++){
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for(int i = 1; i < grid.length; i++){
            for(int j = 1; j < grid[0].length; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];
    }
}
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int dp[] = new int[n];

        dp[0] = grid[0][0];
        for(int j = 1; j < n; j++){
            dp[j] = dp[j - 1] + grid[0][j];
        }
        
        for(int i = 1; i < m; i++){
            dp[0] += grid[i][0];
            for(int j = 1; j < n; j++){
                dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
}

//卡特兰数　h(n)=h(n-1)*(4*n-2)/(n+1)  1, 1, 5, 14...... = C(2n, n) / n + 1;
class Solution {
    public int numTrees(int n) {
        long dp[] = new long[n + 1];
        dp[0] = 1; dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] * (4 * i - 2) / (i + 1);
        }
        return (int)dp[n];
    }
}

TODO

// 从最后一排往上dp
class Solution {
   public static int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = triangle.get(m - 1).size();
        int dp[] = new int[n];

        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(m - 1).get(i);
            System.out.println(dp[i]);
        }
        for (int i = m - 2; i >= 0; i--) {

            for (int j = 0; j <= i; j++) {

                dp[j] = Math.min(dp[j+ 1], dp[j]) + triangle.get(i).get(j);
                // System.out.println(i+":"+ j +"" + "->" + dp[j]);
            }
        }
        return dp[0];
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean [s.length() + 1];
        dp[0] = true;
        for(int  i = 1; i <= s.length(); i ++){
            
            for(int  j = 0; j < i; j++){
                
                if(dp[j] && wordDict.contains(s.substring(j,i))){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    } 
}

todo

// todo again
class Solution {
  public int maxProduct(int[] nums) {
 
    int[] f = new int[nums.length];
    int[] g = new int[nums.length];
    f[0] = nums[0];
    g[0] = nums[0];
    int res = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if(nums[i] < 0){
            int temp = f[i - 1];
            f[i - 1] = g[i - 1];
            g[i - 1] = temp;
        }
        f[i] = Math.max(f[i - 1] * nums[i], nums[i]);
        g[i] = Math.min(g[i - 1] * nums[i], nums[i]);
        res = Math.max(res, f[i]);
    }
    return res;
  }
}

public class Solution {
    public int maximalSquare(char[][] a) {
        if(a.length == 0) return 0;
        int m = a.length, n = a[0].length, result = 0;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1 ; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(a[i-1][j-1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]),dp[i - 1][j - 1]) + 1;
                    result = Math.max(dp[i][j], result); // update result
                }
            }
        }
    return result*result;
    }
}