动态规划 && 贪婪算法

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）

https://www.youtube.com/watch?v=-i2BFAU25Zk

• 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
same : k
different : k * ( k -1 )

• 最多只有2 个是同样的颜色

public int numWays(int n, int k) {
    if( n == 0) return 0;
    if( n == 1) return k;
    /*base case  前两个 相同*/
    int same = k;
    /* base case 前两个不相同 */
    int diff = k * (k - 1)；
    /* 已经有了前两个 之后， 求 i 的概率*/
    for(int i = 3; i<= n ; i++){
        int preDiff = diff;
        diff = (same + diff ) * ( k - 1);
       same = preDiff * 1;
    }
    return diff + same; 
}

8 . House Robber II（213.leetcode）

public int rob(int[] nums) {
    if( nums == null || nums.length == 0) return 0;
    int n = nums.length ;
    int[] rb_rf = new int[ n];
    int[] nrb_rf = new int[n];
    int[] rb_nrf = new int[n];
   int[] nrb_nrf = new int[n];
    rb_rf[0] = nums[0 ];
    for(int i = 1; i<n; i++){
        / * 不符合条件*/
        rb_rf[ i] = nrb_rf[i-1] + nums[i];
        nrb_rf[ i ] = Math.max( nrb_rf[i-1] ,  rb_rf[ i -1 ]  );
        rb_nrf[i] = nrb_nrf[i-1] + nums[i];
        nrb_nrf[ i ] = Math.max( nrb_nrf[i-1] ,  rb_nrf[ i -1 ]  );
    }
    return Math.max( nrb_rf[ n -1] , rb_nrf[ n -1]);
}

9. House Robber III（337.leetcode）

• 树 + DP ： 要了 parent 就不能 要child
  [0, 1] : [not rob , rob]

public int rob(TreeNode root) {
     int[] result = robHelper(root);
     return Math.max( result[0] , result[1]); 
}
public int[] robHelper( TreeNode root){
    if(root == null) return new int[2];
    int[] result = new int[2];
    int[] left = robHelper( root.left);
    int[] right = robHelper(root.right);
    /*要就是result [1] = 上一个state 不能要 */
  result[1] = left[ 0] + right[0] + root.val;
   /* 不哟啊就是 reuslt[ 0 ] , 上一个state 可以要或者 不要 取max*/ 
  result[0] = Math.max(left[0], left[1] ) + Math.max(right[0] , right[1]);
  return result; 
}

10. Paint House II（265. leetcode）

public int minCostII(int[][] costs) {
    if(costs == null || costs.length == 0) return 0;
    int n = costs.length;
    int k = costs[0].length;
    int min1 = -1, min2 = -1;
    for(int i = 0; i<n; i++){
          int last1 = min1 , last2 = min2;
          min1 = -1 ; min2 = -1;
          for(int j =0 ; j<k; j++){
              if(j != last1)
                costs[i][j] = last1 < 0 ？0：costs[i-1][last1];
              else
                 costs[i][j] = last2 < 0? 0 : costs[i -1][last2]
              /* update */
              if( min1 < 0 || costs[i][j] < costs[i][min1])
                    min2 = min1, min1 = j;
              else if(min2 < 0 || costs[i][j] < costs[i][min2])
                    min2 = j;
          }
     }
    return costs[n -1][ min1];
}

11. Best Time to Buy and Sell Stock（121. leetcode）

• buy and sell , 只有一个 transaction

12. Best Time to Buy and Sell Stock III（123. leetcode）

• 这道题一开始没有想出来
• buy and sell , 只可以有2个transaction

解题思路：
得到一组array
buy1 = max(  剩 prev ,  - i )
sell1 = max( 赚prev ， 剩 cur +  i ) /* 因为现在要买*/
buy2 = max ( 剩 prev ， 赚prev - i ) 
sell2 = max( 赚 prev ， 赚 prev + i )
return sell2；

public int maxProfit( int[ ] prices ){
    if(   prices == null || prices.length == 0) return 0;
    int buy1 = Integer.MIN_VALUE;
    int sell1 = 0;
    int buy2 = Integer.MIN_VALUE;
    int sell2 = 0;
    for( int i=0; i< prices.length ; i++){
        /*  这里 buy1 是负数，是为了 后面sell1 减去 buy1*/
        buy1 = Math.max(buy1, - prices[i]);
        sell1 = Math,max( sell1 , prices[ i ] +  buy1 );
        buy2 = Math.max( buy2, sell1 - prices[ i]);
        sell2 = Matn.max( sell2, prices[i] + buy2)
    }
    return sell2;
}

13. Best Time to Buy and Sell Stock IV（188. leetcode）

• buy and sell , 但是有 k 个 transactions

14. Best Time to Buy and Sell Stock with Cooldown（309. leetcode）

15. Edit Distance(leetcode 72. hard)

class Solution {
    public int minDistance(String word1, String word2) {
        // insery
        // delete
        // replace 
        // 求可行性
        // 序列性动态规划 ： 给一个 string， 或数组， 让你求可行性， 序列化推导
        //  状态定义：f[i][j] : 到 word2 的 i，j 的这个letter 的min step
        //  状态转移： f[i][j] = Math.min( )
         char[] s1 = word1.toCharArray();   
        char[] s2 = word2.toCharArray();
        int i, j;
        int m = s1.length;
        int n = s2.length;
        int[][] f = new int[m + 1][n + 1];
         for (i = 0; i <= m; ++i) {
            for (j = 0; j <= n; ++j) {
                if (i == 0) {
                    f[i][j] = j;
                    continue;
                }
                if (j == 0) {
                    f[i][j] = i;
                    continue;
                }
                f[i][j] = Math.min(Math.min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
            
                if (s1[i - 1] == s2[j - 1]) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                  
                }
            }
        }
        return f[m][n];
    }
}

16. One Edit Distance( leetcode medium)

知识点：

• 1： 翻转参数位置
• 2：用 Math.abs( m - n ) 得到两个string 的差值
  思路： 3 种可能性 ， insert, delete, replace 但只能操作一次
• 分情况讨论 ： {replace : s1.length == s2.lenght} ; { delete, insert s1.length != s2.length }
  注意点：
• 短的 string 在前， 保证不会indexoutof bound
• special case : s1 完全等于 s2 没有任何edit

    public boolean isOneEditDistance(String s, String t) {
        // write your code here
        int m = s.length();
        int n = t.length();
        if( Math.abs( m - n) > 1) {
            return false;
        }      
        if( m > n) {
            return isOneEditDistance( t, s);
        }
        for(int i = 0; i< m ; i++ ) {
            if(s.charAt(i) != t.charAt(i)) {
                if( m == n) {
                    return s.substring( i + 1).equals( t.substring( i + 1) );
                    
                } else { // m != n always insert 
                    return s.substring( i ).equals( t.substring(i + 1));
                }
            }
        }
        return m != n;
    }

17. Delete Operation for Two Strings( leetcode medium)

• 难点： s1 向后移， 还是 s2 向后移, 有2 个选择
• dp string 删减字符串类型问题

18. Word Break II( leetcode hard)

• string 可以被分成 str.sibstring(0, len) + str.substring( len);
• 思路：
• 用hashmap 记录 string 可以被分成的 sentence -》 节约时间
• 记忆搜索 + backtracking （DFS 模板）

public ArrayList<String> wordBreak(String s, Set<String> dict) { 
    Map <String , ArrayList< String>> map = new HashMap<String , ArrayList<String>>();
    return wordBreakHelper( s, dict, map )；
}
private ArrayList<String> wordBreakHelper( String str , Set<String> dict, Map <String , ArrayList<String>> map ) {
    /* 找到 结果 直接返回， 以为前面已经比那里过了 这个str 的部分了*/ 
       if( map.contains( str)) {
          return map.get( str );
      }
    / * 没有找到之前相同 的str*/
     ArrayList<String> res = new ArrayList<>();
     for( int len = 1; len < str.length() ; len ++) {
          /*  前半段 str [ 0 , len)*/
          String word = str.substring( 0 ， len);
          if( !dict.contains( str)) {
              continue;
          }
          /* has word in dict , now process suffix  [ len , end)*/
          String suffix = str.substring(len ) ;
          ArrayList<String> segmentations = new wordBreakHelper( suffix , dict , map);
          for( String seg : segmentations) {
                res.add( word + " " + seg);
          }// for 
          
     }// for 
      map.put( str , res );
      return res;
}

19. Triangle ( leetcode Medium)

• 转移方程式： minSum[ x ][ y ] = Math.min( search( x + 1, y) , search(x + 1 , y+ 1));

// declare static value
privat int n ;
privat int[][] minSum ;
private int[][] triangle;

public int minimumTriangle( int[][] triange) {
    // check special case
    if( triangle == null || triangle.length == 0) {
        return - 1;
    }
    if( triangle[0] == null || triangle[0].length == 0) {
        return - 1;
    }
    // built minSum
    this.n  = triangle.length;
    this.triangle = triangle;
    this.minSum = new int[ n][ n];

    for(int i = 0 ; i< n ; i ++) {
        for (int j = 0; j < n ; j ++)  {
              minSum[ i ][ j ] = Integer.MAX_VALUE; 
        }
    }
   return search( 0 , 0 );
}

private int search( int x , int y) {
    // 为什么这里只注意 x ， 而不注意 y  ==>  这里 x 是 j ， col
    if( x  >= n)  {
        return 0;
    }
    //  记录了 底部 的答案
    if( minSum[x][y] != Integer.MAX_VALUE) {
        return minSum[x][y];
    }
    minSum[ x][ y] =Math.min( search( x+ 1 , y) , search( x + 1 , y+ 1 )) + triangle[x][y]; 
    return minSum[ x][y]
}

20. Word Break III ( lintcode Medium)

• 加 space 尽可能多的生成 字典组合
• 这个转移方程式 比较难理解：
• dp[ i][ j ] +=( dp[ i ][ k ] * dp[ k+ 1 ][ j ] )
• dp[i][j] : 到 dp[i][j] 的所有方案总数。

public int wordBreak3(String s, Set<String> dict) { 
     int n = s.length();
      // 1.  remove dup && make all lower case
     String lowS = s.toLowerCase();
    Set<String> lowerDict = new HashSet<String> ();
    for( String str : dict) {
          lowerDict.add( str.toLowerCase() );
    }
    int[][] dp = new int[ n ][ n ];
    // mark all substring in the  dict , use nested loop
    // 不同的 row 就是以不同 的letter 开头
   // 用 2d array represnt 所有在 dict 里的 substring
    for( int i = 0 ; i < n ; i++ ) {
        for( int j = i ; j< n; j++) {
            String sub = s.substring( i , j + 1 );
            if(  lowerDict.contains( sub)) {  
                  dp[ i ][ j ]  = 1;
            } // if 
        } // for 
    } // for 

   for( int i = 0 ; i < n ; i++) {
        //  suffix string 
       for( int j = i ; j < n ; j ++ ) {
               for(int k = i ; k < j ; k ++) { 
                    dp[ i][ j]  +=  (dp[ i ][ k ] + dp[k + 1][ j ]);
              } // for k 
        }  // for i
   } // for j    
return  dp[ 0 ][ n  -1];
} 

21. Wildcard Matching

• 建立 2d array ， 记录 经过的 i , j
• memo [ i ][ j ] : pattern : 0 ~ j 的 substring 和 string 0 ～i 的substring 是否mtch
• visited : 发现current 的path 不valid ， 用于回到路径， 用于记录cur 的路径
• 用 sIndex , pIndex 指针， 指向 s, p
• 记忆化搜索:

public boolean isMatch(String s, String p) {
    if( s == null || p == null) {
        return  false;  
    }
    boolean[ ][ ]  memo = new boolean[s.length() ][p.length()];
    boolean[ ][ ]  visited = new boolean[ s.length()][p.length()];
    return isMatchHelper(s, 0, p , 0, memo, visited); 
}
private boolean isMatchHelper(String s, int sIndex ,
                                              String p , int pIndex ,
                                              boolean[][]  memo,  boolean[][] visited) {
    // 如果p 从 pindex 开始是 空字符串， 那么 s 也必须从 sIndex 
    if( pIndex == p.length() ) {
         return sIndex == s.length(); 
   }
  // 如果 s 从 sIndex 是空，那么p 必须全是 * 
   if( sIndex == s.length()) {
         return allStar( p , pIndex); 
   }

  if( visited[sIndex][ pIndex]) {
      return memo [sIndex][pIndex];
  }
  char sChar = s.charAt( sIndex);
  char pChar = p.charAt( pIndex);
  boolean match ;
  if( pChar == '*') {
      match = isMatchHelper(s ,sIndex , p , pIndex + 1 , memo , visited) && 
                    isMatchHelper( s, sIndex + 1 , p , pIndex , memo , visited );
  }  else {
      match = charMatch( sChar , pChar ) &&  isMatchHelper( s, sIndex + 1
                                                                  p , pIndex + 1 , memo , visited );
  }
  visited[ sIndex ][pIndex] = true;
  memo[sIndex ][pIndex] = match;
   return match;
}

private boolean charMatch( char sChar, char pChar) {
    return (sChar == pChar || pChar == '?');
 }
 private boolean allStar(String p , int pIndex) {
    int i = pIndex;
    while( i < p.length()) {
        if(p.charAt(i) != '*') {
              return false;
        }
        i ++;
    }// while
   return true;
}

DP:

public boolean isMatch(String s, String p) {
    if( s== null || p == null) {
        return false;
    }
    char[ ] sc = s.toCharArry();
    char[ ] pc = s.toCharArray();

    int n = s.length() , m = p.length();
    boolean[][] dp = new boolean[n + 1][ m + 1];
    dp[0][0] = true;
    for( int  j = 1 ; j < dp[0].length() ; j++) {
          if( pc[0][j - 1] == '*') {
                dp[ 0 ][ j ] = dp[ 0][j - 1 ];
           }
     }
for( int i = 1; i< n + 1 ; i++) {
    for( int j = 1; j < m + 1 ; j++) {
         if( sc[ i -1 ] == pc[j - 1] || pc[j - 1] == '?') {
                dp[i][j] = dp[i - 1][j - 1];
         }  
        else  if( pc[ j - 1] == '*' ) {
              dp[i ][ j] = dp[ i ][ j - 1 ]   || dp[ i -1][ j ] ;
              // 这里看 j - 1 ； i - 1
         }
        else {
              dp[ i ][ j ] = false;
        }
    }
  return dp[n][m];
}

}

22. Regular Expression Matching

• 真tm 难

public boolean isMatch(String s, String p ) {
    if( s == null || p == null) {
        return false;
    }
    boolean[][] dp = new boolean[ s.length() + 1][ p.length() + 1];
    dp[0][0] = true;
    for( int j = 1; j < dp.length[0].length() ; j++) {
        if( p.charAt( j - 1 ) == '* ') {
              if( dp[0][ j - 1] == true || ( j > 1 && dp[0][ j -2 ] == true  ))  {
                    dp[0][ j ] = true;
              }
        }
    }
    for( int i =  1; i < dp.length ; i++) {
        for( int j = 1 ; j < dp[0].length ; j ++) {
              if( s.charAt( i -1) == p.charAt( j -1) || p.charAt( j -1) == '.') {
                      dp[i][j] = dp[ i -1 ][ j - 1];
              } 
              if( p.charAt(j - 1) == ' *'  ) {
                     // 前前个 和 s.charAt( i -1 ) 不相等 
                    if( s.charAt( i -1)  != p.charAt(j - 2) && p.charAt( j -2) != '.') {
                         dp[ i ] [ j ] = dp[ i  ][ j - 2];
                     } else {
                         // p.charAt(j -2 ) == '.' or s.charAt( i -1)  == p.charAt(j - 2) 
                          dp[ i][ j] = dp[i - 1][ j ] || //  取 自己 作为 ‘.’ 用
                                         dp[ i ][ j -1 ]  ||  //    取前一个 用
                                          dp[ i ][ j -2 ];   //    取前前一个用
                  } // else 
              }
        }
    }
  return dp[s.length()][p.length()];

23. Next Permutation

• 要求 replacement 是 in-place
• 分析： 如果都是 decs order 那这个 permutation 就没有 next large permutation
  ex : [9, 5, 4, 3, 1]
  从后向前 找到上升点
• 1. 从后向前扫 ， 发现 [ i - 1] < [ i] 的时候 break ， 因为找到了[ i - 1] 要把 i - 1 换到后面去
• 2 再从 后向前扫 找到 左半段 ， 最小的大于 [ i - 1] 的 element ， j
• 3. swap i 和 J
• 4 . 重新排列 i 以后的 element 从小到大

public void nextPermutation(int[] nums){
    if( nums == null || nums.length == 0) {
          return ;
    }
     // 注意这里是 last index
    int i = num.length - 1;
    while( i  - 1 >= 0 && nums[ i  - 1] >= nums[ i]) {
          i --;
    }
    if( i - 1 >= 0 ) {
          int j  = num.length - 1;
          while( j > i  && nums[ j ] <= nums[i - 1]) {
                  j -- ;
          }
          swap( nums ,  i - 1 , j) ;
    }
    swapList( nums ,  i , nums.lenght - 1);
}

private void swap (int[] nums, int left , int right ) {
      int tmp = num[left]l
      nums[left ] = nums[right];
      nums[right] = tmp;
}

private void swapList( int[] nums , int left , int right ) {
      while( left  < right) {
            swap(nums, left , right );
              left ++;
               right --;
      }
}

24. previous permutation

• 从 末尾到头， 找到 下降点 ， 下降点的意义为这个点之前的序列无需改动。
• 然后,将后面的序列变为降序。
• 从下降点开始扫描，找到第一个比她小的数字，交换即可。
  例子： [ 1,3,2,4]

public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) { 
    if( nums == null  || num.size() <= 1) {
        return nums;
    }
    int i = nums.size() - 1;
    while( i > 0 && nums[ i - 1] <= nums[i]) {
            i --;
    } 
    swapList( nums, i , nums.size() -1 );
    if( i  - 1 >= 0) {
        int j = i ;
        while(  nums.get( j) >= nums.get( i -1) ) {
              j ++ ; 
        }
        swapItem(nums , j ,  i -1 );
    }
    return nums; 
}

25. Permutation Index

26.Word Squares

27. Drop Eggs II (求最值)

• f[i][j] 通过规模更小的一些状态 max/min/sum / or 来进行推导
• m : # of eggs
• n : # of floor

public int dropEggs2(int m, int n) {
    int [][] dp = new int[ m+ 1][ n + 1];

    // 初始化在 1 层， 0 层 无论多少个egg ， 结果都是 drop 1 , 0 次
    for( int i = 1 ; i < m + 1 ; i ++) {
          dp[i][ 1] = 1;
          dp[i][0]  = 0;
    }
    // 初始化，只有一个egg 时， 在 j 层， 就是j 个drop
    for( int  j = 0 ; j < n + 1 ; j ++) {
        dp[1][j] = j;
    }

    // 从一个egg 和 2 层开始， 因为 1 层已经被初始化了， 作为初始化条件
    for( int i = 2; i< m + 1; i ++) {
        for( int j = 2; j< n+ 1; j++) {
                dp[i][j] = Integer.Max_VALUE;
                // k 的位置drop , 里面是最糟糕的结果
                for( int k =  1; k <= j ; k++) {
                      dp[i][j] = Math.min( dp[i][j] , 1 + Math.max( dp[ i - 1][ k - 1], dp[ i ][ j - k]) );
                }
          }
    }
    return dp[m][n];
}

28. Paint House （类似于上一题）

• 非滚动数组 做法
• 设定状态： f[i][j] 表示第i所房屋涂色为j时, 前i所房屋的最小花费
• 状态转移方程: f[i][j] = min{f[i-1][k]} +costs[i][j] (k != j)
• 边界: f[0][i] = costs[0][i]
• 答案: min{f[n-1][i]} i = 0, 1, 2

    public int minCost(int[][] costs) {
        // write your code here
        if(costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) {
            return 0;
        }
        int m = costs.length;
        int n = costs[0].length;
        
        int[][] dp = new int[m][3];
        
        for( int j = 0 ; j < 3 ; j ++) {
            dp[0][j] = costs[0][j];
        }     
        for( int i = 1 ; i < m ; i++) {           
                dp[i][0] = Math.min( dp[i-1][1],dp[i-1][2]) + costs[i][0];
                dp[i][1] = Math.min( dp[i - 1][0], dp[i-1][2]) + costs[i][1];
                dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1] ) + costs[i][2];
            
        }
        return Math.min(dp[m-1][0], dp[m-1][1] < dp[m-1][2] ? dp[m-1][1] : dp[m-1][2]);
    }

• 滚动数组做法

  if( costs.length == 0) {
            return 0;
        }
        int[][] dp = new int[2][3];
        for( int  j= 0; j < 3; j++) {
            dp[0][j] = costs[0][j];
        }     
        int old = 0; 
        int now = 0;
        for( int i = 1; i< costs.length ; i++) {
            old = now ;
            now = 1 - old;
            dp[now][0] = Math.min(dp[old][1], dp[old][2]) + costs[i][0];
            dp[now][1] = Math.min(dp[old][0], dp[old][2]) + costs[i][1];
            dp[now][2] = Math.min(dp[old][0], dp[old][1]) + costs[i][2];
        }
        return Math.min(dp[now][0], Math.min(dp[now][1], dp[now][2]));
    }

29.