动态规划 && 贪婪算法

动态规划 && 贪婪算法

1· 剪绳子（14 剑指offer ）

• 需要先从 base case 开始寻找规律 ，绳子长度为 n(2 <=n<=58)， 剪成m 段（2 <= m）, 所以说
  以下是动态规划的解法： n = 1,2,3,4 是 base case
  转移方程式： res[i] = math.max(res[j] + res[ i - j] ) -> j from 1 to i / 2;

public static int maxProduceAfterCutting(int length) {
    if(length == 2)
        return 1;
    if(length == 3)
      return 2;
    if(length == 4)
      return 4;
    int [] res = new int[length + 1]; 
    res[0] = 1;
    res[1] = 1;
    res[2] = 2;
    res [3] = 3; 
    int max = 1; 
    for(int i = 4; i<=length; i++){
        for(int j = 1; j <= i/2; j++){
              int tmp = res[j] * res[ i - j];
              if(tmp > res[i])
                      res[i] = tmp ;
         }
    }
return res[length];
}

• 以下是贪婪算法 的做法, 但是有3个数学的基本证明必须记住
• 假设 ni >= 5 , 3 * ( ni - 3) > ni ? => 2ni > 9 ? 所以说 当 ni >= 5时，把3 切出来 可以乘机最大化
• 当 ni = 4 时， 2* 2 > 3 * 1 , 当 ni = 4 时，把2 切出来，可以乘机最大化
• 当 2 * 2* 2 < 3 * 3， 当既可以切 2个以上的3 ，又可以切2个以上的 2 时，把3 切出来 可以乘机最大化

public static int maxProduceAfterCutting(int length) {
    if(length == 2)
        return 1;
    if(length == 3)
      return 2;
    if(length == 4)
      return 2;
    int timesOf3 = length/3;
    /* 说明可以划出一个 4 */
    if(length - timesOf3 * 3 == 1){
        timesOf3 = timesOf3 -1 ;
    }
  int timesOf2 = (length - 3 * timesOf3) /2;
  return (int) Math.pow(3, timesOf3) * (int)Math.pow(2, timesOf2);
}

2· 匹配2个字符串的模式（19 剑指offer ）

• match pattern 的题型

/*
状态表示： f[i][j]  表示 s[i, ...] 和 p[j, ...] 相匹配
状态转移：
1.  p[j] 是正常字符， f[ i ][ j ] = s[i] = p[j] && f[i+1][j+1]
2.  p[j] 是‘ . ’, f[ i ][ j ] = f[ i+1][ j+1]
3. p[ j + 1 ] 是 ‘ * ’ ， f[ i ][ j ] = f[ i ][ j+2] || f [i+1][ j ]
*/
class Solution {
     int n,m;
      int[][] f ;
    public boolean isMatch(String s, String p) {
        n = s.size();
        m = p.size();
        f = new int[n+1][m+1];
        for(int i=0; i<n+1; i++)
            for( int j =0; j< m+1; j++)
                    f[i][j] = -1;
        return dp(0,0,s,p);
    }

  public dp(int x, int y, String s, String p) {
      if(f[x][y] != null) return f[x][y];
      if( y == m )
            return f [x][y] = x == n;
  }
}

3.Two City Scheduling（1029.leetcode）

• 方一 ：用到了 PriorityQueue 的数据结构

public int twoCitySchedCost(int[][] costs) {
    int countA = 0;
    int countB = 0;
    int res = 0;
    for( int[] city : costs){
        int diff = Math.abs(city[0], city[1]);
        if(city[0] < city[1]){
            res += city[0];
            countA ++;
            pqA.offer(city[0]);
        } else {
          res += city[1];
          countB ++;
          pqB.offer(city[ 1])
        }
    } // for
    while( countA > countB) {
        res += pqA.poll();
        countA --;
        countB++;
    }
    while( countA < countB ){
        res += pqB.poll();
        countB --;
        countA++;
    }
     return res;
}

• 方二 ：用到了 DP 的思想

4. Uncrossed Lines（1035.leetcode）

• dp 思想

public int maxUncrossedLines(int[] A, int[] B) {
    int m = A.length , n = B.length , dp[][] = new int[m + 1][ n + 1];
    for(int i = 11; i<= m ; i++){
        for( int j = 1; j<= n; j++){
            if( A[i - 1][j - 1] == B[i - 1][j - 1])
                dp[i][j] = 1 + dp[i -1 ][j - 1];
            else
                dp = Math.max( dp[i - 1][ j], dp[ i ][j - 1]);
        }
    }
   return dp[m][n];
}

5.Paint House（ 256. leetcode）

• easy 类型
• 转移方程式：
  • paintCurrentRed = min(paintpreviousGreen , paintPreviousBlue) + costs[ i + 1][ 0 ];

public int minCost(int[][] costs){
    if(cost == null || cost.length ==0) return 0;
    int lastR = costs[0][0];
    int lastG = costs[0][1];
    int lastB = costs[0][2];
    for(int i = 1; i < costs.length ; i++){
        int curR = Math.min(lastG, lastB) + costs[i][0];
        int curG = Math.min(lasrR, lastB) + costs[i][1];
        int curB = Math.min(lastR, lastG) + costs[i][2];
        lastR = curR;
        lastG = curG;
        lastB = curB;
    }
    return   Math.min(lastR, lastG< lastB ? lastG : lastB);
}

6. House Robber（198. leetcode）

• step 1. find recursion relation
  • rob(i) = Math.max( rob( i -2 )+ currentHouseV , rob( i -1));
• step 2. recursive( top - down)
  converting the recurrent relation form step1 , 这个算法 重复跑 同样的 i 值 多次， 需要改进

public int rob( int[ ] nums){
    return rob( nums, nums.length - 1);
}
private int rob( int[ ] nums, int i){
    if( i < 0) return 0;
    return Math.max( rob( nums, i -2 ) + nums[i] , rob( nums, i -1 ) );
}

• Step 3. Recursive + memo (top-down). 这里使用一个 array memo 来记录 i 值， runO(n) time. Space complexity O(n)

int [] memo ;
public int rob( int [] nums){
    memo = new int[ nums.length + 1];
    Arrays.fill(memo , -1);
    return rob( nums, nums.length -1 );
}
private int rob( int[] nums, int i){
    if(i < 0) return 0;
    if( memo[i] >= 0) return memo[i];
    int result = Math.max( rob( i -2) + nums[ i]  , rob(i -1));
    memo[i] = result;
    return result;
}

• Step 4. Iterative + memo (bottom-up)
  用for loop 而不用 recurrsion call

public int rob(int[] nums){
    if (nums.length == 0) reutrn 0;
    int[ ] memo = new int[ nums.length + 1];
    memo[0] = 0;
    memo[1] = nums[0];
    for(int i= 1; i < nums.length ; i ++){
        int value = nums[i];
        memo[ i+ 1] = Math.max( memo[i] , memo[ i -1]+ value );
    }
  return memo[nums.length];
}

• Step 5. Iterative + 2 variables (bottom-up)
  因为前面只用了 memo[ i] and memo[ i -1] , so going just 2 steps back. We can hold them in 2 variables instead. This optimization is met in Fibonacci sequence creation and some other problems [to paste links]

/* the order is : prev2 , prev2 , num*/
public int rob(int[] nums){
    if(nums == null || nums.length == 0) return 0;
    int prev1 = 0; 
    int prev2 = 0; 
    for(int num : nums){
          int tmp = prev1;
          
     }
}

7.Paint Fence（ 276.leetcode）

https://www.youtube.com/watch?time_continue=3&v=deh7UpSRaEY