**阅读更多**

# 1 Question-10[★★★★★]

**Regular Expression Matching**

Implement regular expression matching with support for

`'.'`

and`'*'`

.

1 | public class Solution { |

# 2 Question-53[★★★]

**Maximum Subarray**

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array

`[-2,1,-3,4,-1,2,1,-5,4]`

,

the contiguous subarray`[4,-1,2,1]`

has the largest`sum = 6`

.

1 | public class Solution { |

# 3 Question-62[★★]

**Unique Paths**

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

1 | class Solution { |

优化一下空间复杂度

1 | class Solution { |

# 4 Question-70[★★]

**Climbing Stairs**

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1 | class Solution { |

# 5 Question-72[★★★★★]

**Edit Distance**

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

- Insert a character
- Delete a character
- Replace a character

递推表达式(LCS)

`dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1] + 1, dp[i - 1][j] + 1)`

`dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1, dp[i - 1][j] + 1)`

另外注意一下初始化

1 | public class Solution { |

# 6 Question-174[★★★★★]

**Dungeon Game**

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

递推表达式

`dp[row][col]=Math.max(Math.min(dp[row+1][col],dp[row][col+1])-dungeon[row][col],1);`

1 | public class Solution { |

# 7 Question-188[★★★★★]

**Best Time to Buy and Sell Stock IV**

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

递推表达式

`buys[i] = Math.max(buys[i], sells[i - 1] - prices[day])`

`sells[i] = Math.max(sells[i], buys[i] + prices[day])`

1 | public class Solution { |