以下题号均为LeetCode题号，便于查看原题。
10. Regular Expression Matching
题意：实现字符串的正则匹配，包含'.' 和 '*'。'.' 匹配任意一个字符，"*" 匹配 '*' 之前的0个或多个字符。
example：
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
思路：输入字符串 s[0...m] 和 p[0...n]
f[i][j] 表示 s[0..i-1] 和 p[0..j-1] 匹配，我们需要判断 s 和 p 是否匹配，就是求 f[m][n] 的值是否为true，所以要往后更新 f[i][j] 的值。
更新思路如下：
1、if p[j-1]!='*', f[i][j] = f[i-1][j-1] & (s[i-1]==p[j-1] || p[j-1]=='.')
2、if p[j-1]=='*', 看 '*' 匹配多少个字符，即匹配多少个p[j-2]。
如果 '*' 匹配0个字符，此时，p[0...j-1]==p[0...j-3]，f[i][j]=f[i][j-2]；
如果 '*' 匹配1个字符，此时，p[0...j-1]==p[0...j-2]，f[i][j]=f[i][j-1]；
如果 '*' 匹配多个字符，此时，p[0...j-1]=={ p[0: j-2], p[j-2], ... , p[j-2] }，f[i][j]=(s[i-1]==p[j-2] || p[j-2]=='.') & f[i-1][j]
public boolean isMatch(String s, String p)
{
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m+1][n+1];
f[0][0] = true; for (int i = 0; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if(p.charAt(j-1)!='*')
{
f[i][j] = i>0 && f[i-1][j-1] && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.');
}
else
{
f[i][j] = (j>1&&f[i][j-2]) || (i>0&&(s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.')&&f[i-1][j]);
}
}
} return f[m][n];
}
题意：Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
example:
"(()" --> 2
")()())" --> 4
思路：dp[i] 表示在 i 处的匹配的最长子串的长度，维护一个全局max变量，记录到 i 处的最长长度
1、如果s[i]=='('，dp[i]=0
2、如果s[i]==')'，如果s[i-1]=='('，dp[i]=dp[i-2]+2；如果s[i-1]==')' 并且 s[i-dp[i-1]-1]=='('，dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
cmax = 0
dp = [0 for x in range(len(s))]
for i in range(1, len(s)):
if s[i] == ")":
if s[i - 1] == "(":
if i - 2 >= 0:
dp[i] = dp[i - 2] + 2
else:
dp[i] = 2
cmax = max(cmax, dp[i])
else:
if i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
if i - dp[i - 1] - 2 >= 0:
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
else:
dp[i] = dp[i - 1] + 2
cmax = max(cmax, dp[i])
return cmax
44. Wildcard Matching
思路：解法和10.非常像，输入字符串 s[0...m] 和 p[0...n]
f[i][j] 表示 s[0..i-1] 和 p[0..j-1] 匹配，我们需要判断 s 和 p 是否匹配，就是求 f[m][n] 的值是否为true，所以要往后更新 f[i][j] 的值。
example:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
1、如果p[j-1]!='*'，f[i][j]=f[i-1][j-1] & (s[i-1]==p[j-1] || p[j-1]=='?')
2、如果p[j-1]=='*'，f[i][j]=f[i][j-1] || f[i-1][j]
Equation 1). means that if p[j-1] is not *, f(i,j) is determined by if s[0:i-2] matches p[0:j-2] and if (s[i-1]==p[j-1] or p[j-1]=='?').
Equation 2). means that if p[j-1] is *, f(i,j) is true if either f(i,j-1) is true: s[0:i-1] matches p[0:j-2] and * is not used here; or f(i-1,j) is true: s[0:i-2] matches p[0:j-1] and * is used to match s[i-1].
public boolean isMatch(String s, String p) {
int sl = s.length();
int pl = p.length();
boolean[][] a = new boolean[sl+1][pl+1];
a[0][0] = true;
for (int i = 1; i <= pl; i++) {
a[0][i] = p.charAt(i-1) == '*' ? a[0][i-1] : false;
}
for (int i = 1; i <= sl; i++) {
for (int j = 1; j <= pl; j++) {
if (p.charAt(j-1) != '*') {
a[i][j] = a[i-1][j-1] & (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?');
}
else
{
a[i][j] = a[i][j-1] || a[i-1][j];
}
}
}
return a[sl][pl];
}
53. Maximum Subarray
题意：求最大子串和
最优化问题，可以用DP解决，然后考虑构造子问题，可以考虑maxSubArray(int A[], int i, int j)，但是递归方程不太好想到，所以考虑
maxSubArray(int A[], int i)，表示以A[i]结尾的子串的最大和。
所以maxSubArray(A, i) = (maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 ) + A[i];
public int maxSubArray(int[] nums) {
int length = nums.length;
if (length < 1)
return 0;
// int[] dp = new int[length];
// dp[0] = nums[0];
// int max = dp[0];
int curMax = nums[0];
int max = curMax;
for (int i = 1; i < length; i++)
{
// dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
// max = Math.max(max, dp[i]);
curMax = Math.max(curMax+nums[i], nums[i]);
max = Math.max(max, curMax);
}
return max;
}
62. Unique Paths
题意：求从左上到右下有多少不同的路径
p[i][j]表示到(i,j)的路径数，可以观察到，机器人到达(i,j)，要么从左边，要么从上边，所以递归方程为：
p[i][j]=p[i-1][j]+p[i][j-1]
public int uniquePaths(int m, int n) {
int[][] p = new int[m][n];
for(int i = 0; i<m;i++){
p[i][0] = 1;
}
for(int j= 0;j<n;j++){
p[0][j]=1;
}
for(int i = 1;i<m;i++){
for(int j = 1;j<n;j++){
p[i][j] = p[i-1][j]+p[i][j-1];
}
}
return p[m-1][n-1];
}
63. Unique Paths II
题意：在62. 基础上加入障碍，求现在有多少路径。
类似p[i][j]表示到(i,j)的路径数，如果(i,j)=1，则p[i][j]=0，如果(i,j)=0，p[i][j]=p[i-1][j]+p[i][j-1]
需要注意的是边缘情况，即p[0][j]和p[i][0]的值
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
int[][] p = new int[n][m];
for (int i = 0; i < m; i++){
p[0][i] = 1 - obstacleGrid[0][i];
if (p[0][i] == 0) break;
}
for (int j = 0; j < n; j++){
p[j][0] = 1 - obstacleGrid[j][0];
if (p[j][0] == 0) break;
}
for ( int i = 1; i < n; i++){
for (int j = 1; j < m; j++) {
if(obstacleGrid[i][j] == 1)
p[i][j] = 0;
else p[i][j] = p[i-1][j] + p[i][j-1];
}
}
return p[n-1][m-1];
}
64. Minimum Path Sum
题意：找到一条从左上到右下的路径，要使其和最小。
p[i][j]表示到(i,j)的路径和，递归方程为：p[i][j]=min(p[i-1][j],p[i][j-1])+(i,j)
注意边界条件即可
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
return minPathSum(grid, m, n);
}
public int minPathSum(int[][] grid, int m, int n) {
int[][] p = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0)
p[i][j] = grid[i][j];
else if (i == 0 && j > 0)
p[i][j] = p[i][j-1] + grid[i][j];
else if (i > 0 && j == 0)
p[i][j] = p[i-1][j] + grid[i][j];
else
p[i][j] = Math.min(p[i-1][j], p[i][j-1]) + grid[i][j];
}
}
return p[m-1][n-1];
}
70. Climbing Stairs
题意：爬n节楼梯，每步能爬1或2步，求有多少种不同的方法爬到顶端。
p[i]表示到i的路径数，则递归方程为：p[i]=p[i-1]+p[i-2]
public int climbStairs(int n) {
int[] p = new int[n+1];
p[0] = 1;
p[1] = 1;
for (int i = 2; i <= n; i++)
{
p[i] = p[i-1] + p[i-2];
}
return p[n];
}
72. Edit Distance
题意：这题就是求编辑距离。
p[i][j]表示word1[0...i-1]和word2[0...j-1]的编辑距离
1、如果word1[i-1]==word2[j-1]，则p[i][j]=p[i-1][j-1]
2、如果word1[i-1]!=word2[j-1]，则p[i][j]=min(p[i-1][j-1]+1,p[i-1][j]+1,p[i][j-1]+1)
第1个条件好理解，主要说说第2个条件
- Replace
word1[i - 1]byword2[j - 1](dp[i][j] = dp[i - 1][j - 1] + 1 (for replacement)); - Delete
word1[i - 1]andword1[0..i - 2] = word2[0..j - 1](dp[i][j] = dp[i - 1][j] + 1 (for deletion)); - Insert
word2[j - 1]toword1[0..i - 1]andword1[0..i - 1] + word2[j - 1] = word2[0..j - 1](dp[i][j] = dp[i][j - 1] + 1 (for insertion)).
比如p[i][j]=p[i-1][j]+1，将word1[i-1]删掉（一次操作），然后就是看word1[0...i-2]和word2[0...j-1]的编辑距离，即p[i-1][j]
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] p = new int[len1+1][len2+1];
for (int i = 0; i <= len1; i++) {
p[i][0] = i;
}
for (int i = 0; i <= len2; i++) {
p[0][i] = i;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {
p[i][j] = p[i-1][j-1];
}else {
p[i][j] = min(p[i-1][j]+1, p[i][j-1]+1, p[i-1][j-1]+1);
}
}
}
return editDst[len1][len2];
}
85. Maximal Rectangle
题意：在0，1填充的矩形中找出全是1的最大的矩形。
以(i,j)为右下顶点的矩形的最大的面积为[right(i,j)-left(i,j)]*height(i,j)
所以我们维护3个变量，left(i,j)，right(i,j)和height(i,j)
1、left(i,j)记录的是左边界，left(i,j)=max(left(i-1,j), curleft)
2、right(i,j)记录的是右边界，right(i,j)=min(right(i-1,j), curright)
3、height(i,j)记录的是上边界，如果matrix[i][j]=='1'，则height(i,j)=height(i-1,j)+1，否则 height(i,j)=0
public int maximalRectangleUsingDP(char[][] matrix)
{
int m = matrix.length;
int n = matrix[0].length;
int maxA = 0;
int[] left = new int[n];
int[] right = new int[n];
for (int i = 0; i < n; i++)
{ right[i]=n; }
int[] height = new int[n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
height[j] = matrix[i][j]=='1'?height[j]+1:0;
int preleft = 0;
for (int j = 0; j < n; j++)
{
if (matrix[i][j] == '1')
left[j] = Math.max(left[j], preleft);
else{left[j]=0;preleft=j+1;}
}
int preright = n;
for (int j = n-1; j >= 0; j--)
{
if (matrix[i][j] == '1')
right[j] = Math.min(right[j], preright);
else{right[j]=n;preright=j;}
}
for (int j = 0; j < n; j++)
maxA = Math.max((right[j]-left[j])*height[j], maxA);
}
return maxA;
}
87. Scramble String
题意：一个字符串有很多种二叉表示法，判断两个字符串s1，s2是否可以做这样的交换。
使用一个3维数组res[len][len][len+1]，其中第一维为s1的起始索引，第二维为s2的起始索引，第三维为子串的长度。
res[i][j][k]表示的是以i和j分别为s1和s2起点的长度为k的字符串是不是互为scramble。
我们首先是把当前s1[i...i+len-1]字符串劈一刀分成两部分，然后分两种情况：第一种是左边和s2[j...j+len-1]左边部分是不是scramble，以及右边和s2[j...j+len-1]右边部分是不是scramble；第二种情况是左边和s2[j...j+len-1]右边部分是不是scramble，以及右边和s2[j...j+len-1]左边部分是不是scramble。如果以上两种情况有一种成立，说明s1[i...i+len-1]和s2[j...j+len-1]是scramble的。
上面说的是劈一刀的情况，对于s1[i...i+len-1]我们有len-1种劈法，在这些劈法中只要有一种成立，那么两个串就是scramble的。
总结起来递推式是res[i][j][len] = || (res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k]) 对于所有1<=k<len，也就是对于所有len-1种劈法的结果求或运算。因为信息都是计算过的，对于每种劈法只需要常量操作即可完成，因此求解递推式是需要O(len)（因为len-1种劈法）。
如此总时间复杂度因为是三维动态规划，需要三层循环，加上每一步需要线行时间求解递推式，所以是O(n^4)。虽然已经比较高了，但是至少不是指数量级的，动态规划还是有很大有事的，空间复杂度是O(n^3)。
public boolean isScramble(String s1, String s2) {
int n1 = s1.length();
int n2 = s2.length();
if(n1 != n2)
return false;
if(n1 == 0)
return true;
boolean[][][] res = new boolean[n1][n2][n1+1];
for(int i = 0; i<n1; i++){
for(int j=0;j<n2;j++){
res[i][j][1] = (s1.charAt(i)==s2.charAt(j));
}
}
for(int len=2; len <= n1; len++){
for(int i=0; i<= n1-len; i++){
for(int j=0; j<=n2-len; j++){
for(int k = 1; k<len; k++){
res[i][j][len] |= res[i][j][k]&res[i+k][j+k][len-k] || res[i][j+len-k][k]&res[i+k][j][len-k];
}
}
}
}
return res[0][0][n1];
}
91. Decode Ways
题意：求解有多少种不同的解码方式。
res[i]表示s[0...i-1]的不同的解码方式，现在要更新到res[n]。
考虑s(i-2,i-1)的取值范围
1、00,30~90 ---> res[i]=0
2、01-09,27~29,31~99 ---> res[i]=res[i-1]
3、10,20 ---> res[i]=res[i-2]
4、11~19,21~26 ---> res[i]=res[i-1]+res[i-2]
public int numDecodings(String s) {
if (s==null || s.length()==0 || s.charAt(0)=='0'){
return 0;
}
int n = s.length();
int[] res = new int[n+1];
res[0]=1;
res[1]=1;
for(int i=1; i<n; i++){
char ch = s.charAt(i);
if(ch == '0'){
if(s.charAt(i-1)=='1' || s.charAt(i-1)=='2'){ //10, 20
res[i+1]=res[i-1];
}else{ // 00, 30,40,50,60,70,80,90
return 0;
}
}
else{
if(s.charAt(i-1)=='0' || s.charAt(i-1)>'2'){ // 01-09, 31-99
res[i+1]=res[i];
}else if(s.charAt(i-1)=='2' && ch<='6' || s.charAt(i-1)=='1'){ //21-26, 11-19
res[i+1]=res[i]+res[i-1];
}else{ // 27-29
res[i+1]=res[i];
}
}
}
return res[n];
}
96. Unique Binary Search Trees
题意：判断有多少种不同的二叉搜索树结构
可以用动态规划解决。维护两个变量：
G(n)：长度为n的不同的二叉搜索树的数量
F(i,n)：以i为跟结点的长度为n的不同的二叉搜索树的数量
则G(n) = F(1, n) + F(2, n) + ... + F(n, n)，其中G(0)=1,G(1)=1
考虑[1, 2, 3, 4, 5, 6, 7]，跟结点为3，则左子树[1,2]，右子树[4,5,6,7]
F(3,7)=G(2)*G(4)，所以有F(i, n) = G(i-1) * G(n-i)
得出：G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
public int numTrees(int n) {
int [] G = new int[n+];
G[] = G[] = ;
for(int i=; i<=n; ++i) {
for(int j=; j<=i; ++j) {
G[i] += G[j-] * G[i-j];
}
}
return G[n];
}
95. Unique Binary Search Trees II
这道题是求解所有可行的二叉查找树，从Unique Binary Search Trees中我们已经知道，可行的二叉查找树的数量是相应的卡特兰数，不是一个多项式时间的数量级，所以我们要求解所有的树，自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解，也就是N-Queens中介绍的在循环中调用递归函数求解子问题。思路是每次一次选取一个结点为根，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上（每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况），构造好之后作为当前树的结果返回。
public List<TreeNode> generateTrees(int n) {
List<TreeNode> res = new ArrayList<>();
if (n < )
return res;
return generateT(, n);
}
private List<TreeNode> generateT(int left, int right){
List<TreeNode> res = new ArrayList<>();
if (left > right){
res.add(null);
return res;
}
if (left == right){
res.add(new TreeNode(right));
return res;
}
for (int i=left; i<=right; i++){
List<TreeNode> leftList = generateT(left, i-);
List<TreeNode> rightList = generateT(i+, right);
for (TreeNode lnode : leftList){
for (TreeNode rnode : rightList){
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
res.add(root);
}
}
}
return res;
}
121. Best Time to Buy and Sell Stock
题意：给一数组，表示每天的股票的价格，求最多进行一次交易，最大化收益。
最大化第 i 天的最大化收益就是第 i 天的价格 - 以前的最低价格。所以我们维护一个变量min[i]，表示前 i-1 天的最低价格。则：
min[i] = min(min[i-1], prices[i-1])
maxProfit = max(maxProfit, prices[i]-min[i])
public int maxProfit(int[] prices) {
int len = prices.length;
if (len <= 1)
return 0;
int[] min = new int[len];
min[0] = prices[0];
int maxProfit = 0;
for (int i = 1; i < len; i++)
{
min[i] = Math.min(min[i-1], prices[i-1]);
maxProfit = Math.max(maxProfit, prices[i]-min[i]);
}
return maxProfit;
}
123. Best Time to Buy and Sell Stock III
题意：给一数组，表示每天的股票的价格，求最多进行两次交易，最大化收益。
可以在整个区间的每一点切开，然后分别计算左子区间和右子区间的最大值，然后再用O(n)时间找到整个区间的最大值。
O(n^2)的算法很容易想到：
找寻一个点j，将原来的price[0..n-1]分割为price[0..j]和price[j..n-1]，分别求两段的最大收益。
进行优化：
对于点j+1，求price[0..j+1]的最大收益时，很多工作是重复的，在求price[0..j]的最大收益中已经做过了。
类似于上题，可以在O(1)的时间从price[0..j]推出price[0..j+1]的最大收益。
但是如何从price[j..n-1]推出price[j+1..n-1]？反过来思考，我们可以用O(1)的时间由price[j+1..n-1]推出price[j..n-1]。
最终算法：
数组l[i]记录了price[0..i]的最大收益，
数组r[i]记录了price[i..n]的最大收益。
已知l[i]，求l[i+1]是简单的，同样已知r[i]，求r[i-1]也很容易。
最后，我们再用O(n)的时间找出最大的l[i]+r[i]，即为题目所求。
public int maxProfit(int[] prices) {
int len = prices.length;
if (len <= 1)
return 0;
int[] left = new int[len];
left[0] = 0;
// 从前往后
int minPrice = prices[0];
for (int i = 1; i < len; i++)
{
minPrice = Math.min(prices[i-1], minPrice);
left[i] = Math.max(prices[i]-minPrice, left[i-1]);
}
// 从后往前
int max = left[len-1];
int maxPrice = prices[len-1];
int right = 0;
for (int i = len-2; i >= 0; i--)
{
maxPrice = Math.max(maxPrice, prices[i+1]);
right = Math.max(right, maxPrice-prices[i]);
max = Math.max(max, right+left[i]);
}
return max;
}
188. Best Time to Buy and Sell Stock IV
题意：在最多进行k次交易的前提下，求最大收益。
我们还是使用“局部最优和全局最优解法”。我们维护两种量，一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]），另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少（local[i][j]）。下面我们来看递推式，全局的比较简单，
也就是去当前局部最好的，和过往全局最好的中大的那个（因为最后一次交易如果包含当前天一定在局部最好的里面，否则一定在过往全局最优的里面）。
全局（到达第i天进行j次交易的最大收益） = max{局部（在第i天交易后，恰好满足j次交易），全局（到达第i-1天时已经满足j次交易）}
对于局部变量的维护，递推式是
也就是看两个量，第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），第二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了）。
局部（在第i天交易后，总共交易了j次） = max{情况2，情况1}
情况1：在第i-1天时，恰好已经交易了j次（local[i-1][j]），那么如果i-1天到i天再交易一次：即在第i-1天买入，第i天卖出（diff），则这不并不会增加交易次数！【例如我在第一天买入，第二天卖出；然后第二天又买入，第三天再卖出的行为 和 第一天买入，第三天卖出 的效果是一样的，其实只进行了一次交易！因为有连续性】
情况2：第i-1天后，共交易了j-1次（global[i-1][j-1]），因此为了满足“第i天过后共进行了j次交易，且第i天必须进行交易”的条件：我们可以选择1：在第i-1天买入，然后再第i天卖出（diff），或者选择在第i天买入，然后同样在第i天卖出（收益为0）。
public int maxProfit(int k, int[] prices) {
int len = prices.length;
if (len == 0) return 0;
if (k >= len / 2) return quickSolve(prices);
int [][] local = new int[len][k+1];
int [][] global = new int[len][k+1];
for (int i = 1; i < len; i++)
{
int diff = prices[i]-prices[i-1];
for (int j = 1; j <= k; j++)
{
local[i][j] = Math.max(global[i-1][j-1]+Math.max(0,diff), local[i-1][j]+diff);
global[i][j] = Math.max(global[i-1][j], local[i][j]);
}
}
return global[len-1][k];
}
private int quickSolve(int[] prices) {
int len = prices.length, profit = 0;
for (int i = 1; i < len; i++)
// as long as there is a price gap, we gain a profit.
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;
}
264. Ugly Number II
题意：求第n个ugly数。ugly数定义为因子只有2，3，5的数，如：1，2，3，4，5，6，8，9，10，12等，定义1为第一个ugly数。
k[n-1]为第n个ugly数，则k[0]=1
k[1]=min(k[0]*2,k[0]*3,k[0]*5) -> k[0]*2
k[2]=min(k[1]*2,k[0]*3,k[0]*5) -> k[0]*3
k[3]=min(k[1]*2,k[1]*3,k[0]*5) -> k[1]*2
public int nthUglyNumber(int n)
{
int[] k = new int[n];
k[0] = 1;
int t1 = 0, t2 = 0, t3 = 0;
for (int i = 1; i < n; i++)
{
k[i] = min(k[t1]*2, k[t2]*3, k[t3]*5);
if (k[i]==k[t1]*2) t1 += 1;
if (k[i]==k[t2]*3) t2 += 1;
if (k[i]==k[t3]*5) t3 += 1;
}
return k[n-1];
}
private int min(int a, int b, int c)
{
a = a < b ? a : b;
return a < c ? a : c;
}
279. Perfect Squares
题意：求数n是最少多少个平方数的和。
p[i]表示由p[i]个平方数构成数i，其中p[i]是最小的值，则p[i]=min(p[k]+p[i-k])，k>=1且k<=i.
我们可以再优化下k的取值，将k取值为平方数，则p[i]=min(1+p[i-k])，k=j*j且k<=i
public int numSquares(int n)
{
int[] p = new int[n+1];
p[0] = 0;
for (int i = 1; i <= n; i++)
{
p[i] = n; for (int j = 1; j*j <= i; j++)
p[i] = Math.min(p[i], p[i-j*j]+1);
}
return p[n];
}
300. Longest Increasing Subsequence
题意：找到数组nums最长递增子序列，求出长度。
p[i]为包含索引 i 的最长递增子序列的长度，则更新p[i]=max(p[j]+1, p[i])，nums[i]>nums[j]，j from 0 to i-1
public int lengthOfLIS(int[] nums)
{
if (nums == null || nums.length == 0)
return 0;
int max = 0;
int[] p = new int[nums.length];
for (int i = 0; i < nums.length; i++)
{
p[i] = 1;
for (int j = 0; j < i; j++)
{
if (nums[i] > nums[j] && p[j] + 1 > p[i])
{
p[i] = p[j] + 1;
}
}
max = Math.max(max, p[i]);
}
return max;
}
309. Best Time to Buy and Sell Stock with Cooldown
题意：
给定一个数组，第i个元素代表某只股票在第i天的价格。
设计一个算法计算最大收益。你可以完成多次交易（亦即，多次买入、卖出同一只股票），需要满足下列限制：
- 你不可以在同一时间参与多个交易（亦即，在买入股票之前必须卖出）。
- 在卖出股票之后，你不可以在第二天马上买入。
这道题比较麻烦的是有个cooldown的限制，其实本质也就是买与卖之间的限制。对于某一天，股票有三种状态: buy, sell, cooldown, sell与cooldown我们可以合并成一种状态，因为手里最终都没股票，最终需要的结果是sell，即手里股票卖了获得最大利润。所以我们可以用两个DP数组分别记录当前持股跟未持股的状态。
对于当天最终未持股的状态，最终最大利润有两种可能，一是今天没动作跟昨天未持股状态一样，二是昨天持股了，今天卖了。所以我们只要取这两者之间最大值即可，表达式：sells[i] = max(sells[i-1], buys[i-1]+price[i])
对于当天最终持股的状态，最终最大利润有两种可能，一是今天没动作跟昨天持股状态一样，二是前天还没持股，今天买了股票，这里是因为cooldown的原因，所以今天买股要追溯到前天的状态。我们只要取这两者之间最大值即可，表达式：buys[i] = max(buys[i-1], sells[i-2]-price[i])
第二种思路：
/*
* 每一天有3种状态，buy,sell,rest
* buy[i]表示第i天买入后的最大收益，sell[i]表示第i天卖出后的最大收益，rest[i]表示第i天不做操作的最大收益
* buy[i] = max(buy[i-1]-price[i], sell[i-1]-price[i], rest[i-1]-price[i], buy[i-1])
* sell[i] = max(buy[i-1]+price[i], sell[i-1]+price[i], rest[i-1]+price[i], sell[i-1])
* rest[i] = max(buy[i-1], sell[i-1], rest[i-1])
* 然后去除上述不合理的情况
* buy[i]<=sell[i],rest[i]<=sell[i],所以rest[i] = sell[i-1]
* buy[i] = max(buy[i-1]-price[i], sell[i-1]-price[i], sell[i-2]-price[i], buy[i-1])
* sell[i] = max(buy[i-1]+price[i], sell[i-1]+price[i], sell[i-2]+price[i], sell[i-1])
* 因为 buy[i-1]-price[i] <= buy[i-1], 昨天卖了，今天不可能再买
* 所以 buy[i] = max(sell[i-2]-price[i], buy[i-1])
* 因为 昨天和前天卖了，今天不可能再卖
* 所以 sell[i] = max(buy[i-1]+price[i], sell[i-1])
*
* 所以有递推式
* buy[i] = max(sell[i-2]-price[i], buy[i-1])
* sell[i] = max(buy[i-1]+price[i], sell[i-1])
* */
/*
* buy[i] = max(sell[i-2]-price, buy[i-1])
* sell[i] = max(buy[i-1]+price, sell[i-1])
* */
public int maxProfit(int[] prices)
{
int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
for (int i = 0; i < prices.length; ++i)
{
prev_buy = buy;
buy = Math.max(prev_sell-prices[i], prev_buy);
prev_sell =sell;
sell = Math.max(prev_buy+prices[i], prev_sell);
}
return sell;
}
338. Counting Bits
题意：计算二进制表示中有多少个1.
先写写看，找找规律。0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4，发现 0,1,1,2,1,2,2,3, | 1,2,2,3,2,3,3,4 后半部分正好是前半部分加1。类似，0,1,1,2,| 1,2,2,3 也是这种规律。所以，二进制每多一位就把结果数组中所有的结果都加一，再放回结果数组中。
public int[] countBits(int num)
{
if (num == 0) return new int[]{0};
int[] res = new int[num+1];
int count = 0;
while (true)
{
int len = count+1;
for (int j = 0; j < len; j++)
{
res[++count] = res[j]+1;
if (count >= num) return res;
}
}
}