动态规划专题

class Solution {
    public int integerBreak(int n) {
       int[] dp = new int[n + 1];
       dp[1] = 1;
       for(int i = 2; i <= n; i ++) {
           for(int j = 1; j < i; j ++) {
               dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
           }
       }
       return dp[n];
    }
}

//BFS


class Solution {
  public int numSquares(int n) {
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    q.offer(0);
    visited.add(0);
    int depth = 0;
    while(!q.isEmpty()) {
        int size = q.size();
        depth++;
        while(size-- > 0) {
            int u = q.poll();
            for(int i = 1; i*i <= n; i++) {
                int v = u+i*i;
                if(v == n) {
                    return depth;
                }
                if(v > n) {
                    break;
                }
                if(!visited.contains(v)) {
                    q.offer(v);
                    visited.add(v);
                }
            }
        }
    }
    return depth;
  }
}

//DP
public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for(int i = 1; i <= n; ++i) {
        int min = Integer.MAX_VALUE;
        int j = 1;
        while(i - j*j >= 0) {
            min = Math.min(min, dp[i - j*j] + 1);
            ++j;
        }
        dp[i] = min;
    }        
    return dp[n];
}

class Solution {
    public int numDecodings(String s) {
        int[] dp = new  int[s.length()+1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0: 1;
        
        for(int i =2;i<=s.length();i++){
            int onedig = Integer.valueOf(s.substring(i-1,i));
            int twodig = Integer.valueOf(s.substring(i-2,i));
            if(onedig > 0){
                dp[i] += dp[i-1];
            }
            if(twodig >=10 && twodig <= 26){
                dp[i] += dp[i-2];
            }
            
        }
        return dp[s.length()];
    }
}

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


//非递归
class Solution {
   public int rob(int[] num) {
    int prevNo = 0;
    int prevYes = 0;
    for (int n : num) {
        int temp = prevNo;
        prevNo = Math.max(prevNo, prevYes);
        prevYes = n + temp;
    }
    return Math.max(prevNo, prevYes);
  }
}

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
  }
    
    private int rob(int[] num, int lo, int hi) {
      int include = 0, exclude = 0;
      for (int j = lo; j <= hi; j++) {
          int i = include, e = exclude;
          include = e + num[j];
          exclude = Math.max(e, i);
     }
      return Math.max(include, exclude);
  }
   
}

public class Solution {

    public static int getMaxValue(int[] weight, int[] value, int w, int n) {
        int[][] table = new int[n + 1][w + 1];
        for (int i = 1; i <= n; i++) { //物品
            for (int j = 1; j <= w; j++) {  //背包大小
                if (weight[i] > j) {        
                        //当前物品i的重量比背包容量j大，装不下，肯定就是不装
                    table[i][j] = table[i - 1][j];
                    // System.out.print(table[i][j]+ " ");
                } else { //装得下，Max{装物品i， 不装物品i}
                    table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i]] + value[i]);
                    //System.out.print(table[i][j]+ " ");
                }
            }
            // System.out.println();
        }
        return table[n][w];
    }

    public static void main(String[] args) {

        int n = 5, w = 10;                    //物品个数，背包容量
        int[] value = {0, 6, 3, 5, 4, 6};     //各个物品的价值
        int[] weight = {0, 2, 2, 6, 5, 4};    //各个物品的重量
        System.out.println(getMaxValue(weight,value,w,n));

    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
       
        int[] dp = new int[nums.length];//含义dp[i]为：以nums[i]元素为结尾的最长上升子序列的数目
        Arrays.fill(dp,1);  //默自己为最长上升序列 所以默认1
        int max = dp[0];//用一个max来记录，否则最后要for遍历一下 dp数组寻找最大值
        for(int i=1; i<nums.length; i++){
             for(int j=0; j<i; j++){     
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1); //加1必须放在里面
                }
                 max = Math.max(max,dp[i]);
            }
        }
      
        return max;
    }
}

 

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums==null || nums.length==0) {
            return false;
        }
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        if(sum%2 != 0) {
            return false;
        }
        return this.subsetSum(nums, sum/2);
    }
    
    private boolean subsetSum(int[] nums, int target) {
        
        int row = nums.length, col = target + 1;
        boolean[][] dp = new boolean[row][col];
        dp[0][0] = true;
        for(int i=1; i<row; i++) {
            dp[i][0] = true;
        }
        for(int i=1; i<col; i++) {
            if(i == nums[0]) {
                dp[0][i] = true;
            }
        }
        for(int i=1; i<row; i++) {
            for(int j=1; j<col; j++) {
                if(j >= nums[i]) {
                    dp[i][j] = dp[i-1][j - nums[i]] || dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[row-1][col-1];
    }
}

class Solution {
public static int coinChange(int[] coins, int amount) {
    if (coins == null || coins.length == 0 || amount <= 0)
        return 0;
    int[] minNumber = new int[amount + 1];
    for (int i = 1; i <= amount; i++) {
        minNumber[i] = Integer.MAX_VALUE;//先赋值是为了后面比较
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i && minNumber[i - coins[j]] != Integer.MAX_VALUE)
                minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);
        }
    }
    if (minNumber[amount] == Integer.MAX_VALUE)
        return -1;
    else
        return minNumber[amount];
}
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        Boolean[] dp = new Boolean[s.length()];
        return dfs(s, set, 0, dp);
    }
    
    private boolean dfs(String s, Set<String> dict, int idx, Boolean[] dp){
        if(idx == s.length()) return true;
        
        if(dp[idx] != null) return dp[idx];
        
        for(int i=idx+1; i<=s.length(); i++){
            if(dict.contains(s.substring(idx, i)) && dfs(s, dict, i, dp)){
                return dp[idx] = true;
            }
        }
        return dp[idx] = false;
    }
}