42. 接雨水

思路：最直白的思路就是将每一位上的积水累加起来就是最终答案。
问题转化为计算每一位**i**上的积水，则需要找到该位置左侧的最高点(包含当前位置高度)leftMax(i)，和该位置最右侧的最高点(包含当前位置)rightMax(i)，取其中比较小的值min(leftMax(i),rightMax(i))再减去当前高度height(i)就是当前位置i的积水，所以问题进一步转化为快速求出当前位置i左侧的最大值和右侧的最大值，到这里就相对简单点了。

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3) return 0;
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        leftMax[0] = height[0];
        int sum = 0;
        rightMax[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1],height[i]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        for (int i = 0; i < height.length; i++) {
            sum += Math.min(leftMax[i],rightMax[i]) - height[i];
        }
        return sum;
    }
}

单调栈法

5. 最长回文子串

思路：考察索引i和j之间的字符串是否是回文串得到状态方程：
dp[i][j] = chars[i] == chars[j] && dp[i + 1][j - 1];，考虑一下边界条件，必须满足i + 1 <= j - 1,即j - i >= 2,如果j - i < 2，则dp[i][j] = chars[i] == chars[j]
综上：
j-i<2时：dp[i][j] = chars[i] == chars[j]

j-i>=2时：dp[i][j] = chars[i] == chars[j] && dp[i + 1][j - 1];

class Solution {
  public String longestPalindrome(String s) {
   //   dp[i][j] = chars[i - 1] == chars[j + 1] && dp[i + 1][j - 1];
      if (s == null || s.length() < 2) return s;
      boolean[][] dp = new boolean[s.length()][s.length()];
      char[] chars = s.toCharArray();
      int start = 0, maxLen = 1;
      for (int j = 0; j < chars.length; j++) {
          for (int i = 0; i <= j; i++) {
              if (j - i < 2){
                  dp[i][j] = chars[i] == chars[j];
              }else {
                  dp[i][j] = chars[i] == chars[j] && dp[i + 1][j - 1];
              }
              if (dp[i][j] && j - i + 1 > maxLen) {
                  start = i;
                  maxLen = j - i + 1;
              }
          }
      }
      return s.substring(start, maxLen + start);
  }
}

将上面代码化简一下：

class Solution {
//   dp[i][j] = chars[i - 1] == chars[j + 1] && dp[i + 1][j - 1];
  public String longestPalindrome(String s) {
      if (s == null || s.length() < 2) return s;
      boolean[][] dp = new boolean[s.length()][s.length()];
      char[] chars = s.toCharArray();
      int start = 0, maxLen = 1;
      for (int j = 0; j < chars.length; j++) {
          for (int i = 0; i <= j; i++) {
              dp[i][j] = chars[i] == chars[j]
                      && ((j - i <= 2) || dp[i + 1][j - 1]);
              if (dp[i][j] && j - i + 1 > maxLen) {
                  maxLen = j - i + 1;
                  start = i;
              }
          }
      }
      return s.substring(start, maxLen + start);
  }
}

中心扩散法：主要考虑从中间一个元素还是两个元素扩散。

class Solution {
  public String longestPalindrome(String s) {
      if (s == null || s.length() == 0) return s;
      char[] chars = s.toCharArray();
      int n = s.length();
      String res = "";
      for (int i = 0; i < n; i++) {
          String s1 = centerSpread(chars, i, i);
          String s2 = centerSpread(chars, i, i + 1);
          String s3 = s1.length() < s2.length() ? s2 : s1;
          res = s3.length() < res.length() ? res : s3;
      }
      return res;
  }
  private String centerSpread(char[] chars, int i, int j) {
      int l = i, r = j;
      int n = chars.length;
      while(l >= 0 && r < n) {
          if (chars[l] == chars[r]) {
              l--;
              r++;
          } else {
              break;
          }
      }
      return new String(chars, l + 1, r - 1 - l);
  }
}

72. 编辑距离

思路：动态规划，定义dp[i][j]为word1前i个字符转换成word2前j个字符所需要的最少操作。
动态规划(一) - 图4

class Solution {
  public int minDistance(String word1, String word2) {
      int n1 = word1.length();
      int n2 = word2.length();
      //dp[i][j] 代表word1前i位，和word2前j位，最少操作数。
      int[][] dp = new int[n1+ 1][n2 + 1];
      //dp[i][j] = dp[i-1][j-1]
      //dp[i][j] = 1+Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
      for (int i = 0; i < n1 + 1; i++) {
          dp[i][0] = i;
      }
      for (int j = 0; j < n2 + 1; j++) {
          dp[0][j] = j;
      }

      for (int i = 1; i < n1 + 1; i++) {
          for (int j = 1; j < n2 + 1; j++) {
              if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                  dp[i][j] = dp[i - 1][j - 1];
              } else {
                  dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]),dp[i - 1][j - 1]);
              }
          }
      }
      return dp[n1][n2];

  }
}

1143. 最长公共子序列

思路：考察text1的前i个字符和text2的前j个字符的最长公共子串，动态方程就可以写出来了。

class Solution {
  public int longestCommonSubsequence(String text1, String text2) {
      //dp[i][j] = dp[i - 1][j - 1]+1 当text1[i] == text2[j]
      //dp[i][j] = max{dp[i - 1][j],dp[i][j - 1]} 当text1[i] != text2[j]
      if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) return 0;
      char[] chars1 = text1.toCharArray();
      char[] chars2 = text2.toCharArray();
      int[][] dp = new int[chars1.length + 1][chars2.length + 1];
      for (int i = 1; i < chars1.length + 1; i++) {
          for (int j = 1; j < chars2.length + 1; j++) {
              if (chars1[i - 1] == chars2[j - 1]) {
                  dp[i][j] = dp[i - 1][j - 1] + 1;
              } else {
                  dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
              }
          }
      }
      return dp[chars1.length][chars2.length];
  }
}

32. 最长有效括号

class Solution {
  public int longestValidParentheses(String s) {
      //dp[i]表示以i索引位置结尾的最长有效括号的长度
      //当s[i]='(' 时  dp[i] =0;
      //dp[i] = dp[i-1]+dp[i-dp[i-1]-2] + 2 当s[i-dp[i-1]-1]='(',s[i]=')'
      if (s == null || s.length() < 2) return 0;
      int n = s.length(), max = 0;
      char[] chars = s.toCharArray();
      int[] dp = new int[n];

      for (int i = 1; i < n; i++) {
          if (chars[i] == ')' && i - dp[i - 1] - 1 >= 0 && chars[i - dp[i - 1] - 1] == '(') {
              int pre = i - dp[i - 1] - 2 < 0 ? 0 : dp[i - dp[i - 1] - 2];
              dp[i] = 2 + dp[i - 1] + pre;
              max = Math.max(max,dp[i]);
          }
      }
      return max;
  }
}

1048. 最长字符串链

方法1：朴素法

class Solution {
      public int longestStrChain(String[] words) {
          if (words == null || words.length == 0) return 0;
          //以word[i]结尾的chain的最大的长度
          int[] dp = new int[words.length];
          Arrays.fill(dp, 1);
          int max = 1;
          Arrays.sort(words, new Comparator<String>() {
              @Override
              public int compare(String o1, String o2) {
                  return o1.length() - o2.length();
              }
          });
          for (int i = 0; i < words.length; i++) {
              for (int j = 0; j < i; j++) {
                  if (contains(words[i], words[j])) {
                      dp[i] = Math.max(dp[i], dp[j] + 1);
                      max = Math.max(max, dp[i]);
                  }
              }
          }
          return max;
      }

      private boolean contains(String a, String b) {
          if (a.length() != b.length() + 1) return false;
          int i = 0, j = 0;
          while (i != a.length() && j != b.length()) {
              if (a.charAt(i) == b.charAt(j)) {
                  i++;
                  j++;
              } else {
                  i++;
              }
          }
          return j == b.length();
      }
  }

剑指 Offer 47. 礼物的最大价值

思路：定义dp[i][j]为走到grid[i-1][j-1]的最大价值，则状态方程为：
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

class Solution {
  public int maxValue(int[][] grid) {
      //dp[i][j] = max{dp[i-1][j],dp[i][j-1]} + grid[i][j]
      if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
      int m = grid.length, n = grid[0].length;
      int[][] dp = new int[m + 1][n + 1];
      for (int i = 1; i < m + 1; i++) {
          for (int j = 1; j < n + 1; j++) {
              dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
          }
      }
      return dp[m][n];
  }
}

64. 最小路径和

和上一题如出一辙啊。。

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

62. 不同路径

class Solution {
  public int uniquePaths(int m, int n) {
      //定义dp[i][j] 为到grid[i][j] 不同路径个数
      //dp[i][j] = dp[i-1][j]+dp[i][j-1]
      if (m <= 0 || n <= 0) return 0;
      int[][] dp = new int[m + 1][n + 1];
      dp[0][1] = 1;//主要为了初始化dp[1][1] = 1
      for (int i = 1; i < m + 1; i++) {
          for (int j = 1; j < n + 1; j++) {
              dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
          }
      }
      return dp[m][n];
  }
}

121. 买卖股票的最佳时机

朴素法：考虑每一天都有可能卖股票，则当天的最大利润就是当天价格减去前面最小的价格。

class Solution {
  public int maxProfit(int[] prices) {
      if (prices == null || prices.length == 0) return 0;
      int[] profits = new int[prices.length];
      int max = 0, minPrice = Integer.MAX_VALUE;
      for (int i = 0; i < prices.length; i++) {
          if (prices[i] > minPrice) {
              max = Math.max(max,prices[i] - minPrice);
          } else {
              minPrice = prices[i];
          }
      }
      return max;
  }
}

dp法：可以把问题转换成求最大连续子数组和

class Solution {
  public int maxProfit(int[] prices) {
      if (prices == null || prices.length < 2) return 0;
      int[] profits = new int[prices.length - 1];
      for (int i = 0; i < prices.length - 1; i++) {
          profits[i] = prices[i + 1] - prices[i];
      }
      //求profits最大连续子数组和
      int[] dp = new int[profits.length];
      dp[0] = profits[0];
      int max = dp[0];

      for (int i = 1; i < dp.length; i++) {
          dp[i] = Math.max(profits[i], dp[i - 1] + profits[i]);
          max = Math.max(max,dp[i]);
      }
      return max < 0 ? 0 : max;
  }
}

53. 最大子序和

class Solution {
  public int maxSubArray(int[] nums) {
      if (nums == null || nums.length == 0) return 0;
      //dp[i] 以i结尾的最大子序和
      int[] dp = new int[nums.length];
      dp[0] = nums[0];
      int max = dp[0];
      for (int i = 1; i < nums.length; i++) {
          dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
          max = Math.max(max,dp[i]);
      }
      return max;
  }
}

322. 零钱兑换

class Solution {
  public int coinChange(int[] coins, int amount) {
      if (coins == null || coins.length == 0 || amount == 0) return 0;
      //dp[i]表示兑换i元需要的最小硬币个数
      // dp[i]=min{dp[i-coins[i]]} + 1
      int[] dp = new int[amount + 1];
      Arrays.fill(dp, amount + 1);
      dp[0] = 0;
      for (int i = 1; i < amount + 1; i++) {
          for (int j = 0; j < coins.length; j++) {
              if (i - coins[j] < 0) continue;
              dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
          }
      }
      return dp[amount] == amount + 1 ? -1 : dp[amount];
  }
}

面试题 08.11. 硬币

思路：
dp[i][j]表示使用coins的前i个币，来凑齐数目为j的金额，则有
dp[i][j]=dp[i-1][j]+dp[i-1][j-coins[i]+dp[i-1][j-2*coins[i]+dp[i-1][j-k*coins[i]]…. 当j-k*coins[i] >=0时
令j= j-coins[i]则有
dp[i][j-coins[i]=dp[i-1][j-coins[i]]+dp[i-1][j-2*coins]+dp[i-1][j-k*coins[i]]，代入第一个式子得到状态方程：
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]]

class Solution {
  public int waysToChange(int n) {
      if (n <= 0) return 0;
      int[] coins = new int[] {1, 5, 10, 25};
      //dp[i][j] = dp[i-1][j-k * coins[i]] res:dp[4][n]
      int[][] dp = new int[4][n + 1];
      for (int j = 0; j < n + 1; j++) {
          dp[0][j] = 1;
      }
      for (int i = 1; i < 4; i++) {
          for (int j = 0; j < n + 1; j++) {
                  dp[i][j] = dp[i - 1][j];
                  if (j - coins[i] >= 0) {
                      dp[i][j] = (dp[i][j] + dp[i][j - coins[i]]) % 1000000007;
                  }
          }
      }
      return dp[3][n];
  }
}