逆序对
629 K Inverse Pairs Array
Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
思路， 假设 dp[n,k] 代表1-n个数组成的k个逆序对的个数，那么 dp[n,k] = dp[n-1,k] +dp[n-1,k-1]…+ dp[n-1, k-(n-1)]
因为 对 1-（n-1）个数字，我们可以把数字n加到1-（n-1）中的任何一个间隙， 比如加到最后， 那么相当于dp[n-1, k]个方案。。因为加了n最多再产生n-1个逆序对，那么要保证dp[n-1,?]的逆序对大于等于 k-(n-1). 由这个递推式，我们需要O（nkk）。 其实可以再化简：
dp[i][0] = dp[i-1][0] (creates 0 inverse pair)
dp[i][1] = dp[i-1][0] (1) + dp[i-1][1] (0) = dp[i][0] + dp[i-1][1]
dp[i][2] = dp[i-1][0] (2) + dp[i-1][1] (1) + dp[i-1][2] (0) = dp[i][1] + dp[i-1][2]
.
.
.
dp[i][4] = dp[i-1][0] (4) + dp[i-1][1] (3) + dp[i-1][2] (2) + dp[i-1][3] (1) + dp[i-1][4] (0) = dp[i][3] + dp[i-1][4]
得出：
dp[i][j] = dp[i][j-1] +dp[i-1][j] (j < i)
dp[i][j] = dp[i][j-1] +dp[i-1][j] - dp[i-1][j - i] (else)
class Solution {
public:
int kInversePairs(int n, int k) {
vector<vector<int>> dp(n+1, vector<int>(k+1));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i){
dp[i][0] = 1;
for(int j = 1; j <= k; ++j){
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod;
if(j - i >= 0){
dp[i][j] = (dp[i][j] - dp[i-1][j-i] + mod) % mod;
//It must + mod, If you don't know why, you can check the case 1000, 1000
}
}
}
return dp[n][k];
}
private:
const int mod = pow(10, 9) + 7;
};
字符串
10. Regular Expression Matching
Implement regular expression matching with support for ‘.’ and ‘*’.
’.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be: bool isMatch(const char *s, const char *p)
Some examples: isMatch(“aa”,”a”) ? false isMatch(“aa”,”aa”) ? true isMatch(“aaa”,”aa”) ? false isMatch(“aa”, “a”) ? true isMatch(“aa”, “.”) ? true isMatch(“ab”, “.”) ? true isMatch(“aab”, “ca*b”) ? true
class Solution {
public:
bool isMatch(string s, string p) {
int m=s.length();
int n=p.length();
vector<vector<bool>>dp(m+1,vector<bool>(n+1,false));
dp[0][0]=true;
for(int i=0;i<=m;i++){
for(int j=1;j<=n;j++){
if(p[j-1]!='*'){
dp[i][j]=i>0&&dp[i-1][j-1]&&(s[i-1]==p[j-1]||p[j-1]=='.');
}
else{
dp[i][j]=dp[i][j-2]||(i>0&&dp[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.'));
}
}
}
return dp[m][n];
}
};
5. Longest Palindromic Substring
输入一个字符串，返回最长的回文子串
最长回文子串， 用dp[i][j]代表子串i-j是不是回文。可以很容易得到递推式。 根据递推式，从n-0 遍历，如果是回文的话，并且 j-i长度大于当前子串，那么更新最大回文子串。
class Solution {
public:
string longestPalindrome(string s) {
string res = "";
if(s.size() < 1){
return res;
}
int n = s.size();
bool dp[n][n];
for(int i = n - 1; i >= 0; i--){
for(int j = i; j < n; j++){
dp[i][j] = (s[i] == s[j]) && (j - i < 3 || dp[i + 1][j - 1]);
if(dp[i][j] && (j - i + 1) > res.size()){
res = s.substr(i, j - i + 1);
}
}
}
return res;
}
};
另一解法： 这道题是比较常考的题目，求回文子串，一般有两种方法。 第一种方法比较直接，实现起来比较容易理解。基本思路是对于每个子串的中心（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙）往两边同时进行扫描，直到不是回文串为止。假设字符串的长度为n,那么中心的个数为2n-1(字符作为中心有n个，间隙有n-1个）。对于每个中心往两边扫描的复杂度为O(n),所以时间复杂度为O((2n-1)*n)=O(n^2),空间复杂度为O(1)，代码如下：
public String longestPalindrome(String s) {
if(s == null || s.length()==0)
return "";
int maxLen = 0;
String res = "";
for(int i=0;i<2*s.length()-1;i++)
{
int left = i/2;
int right = i/2;
if(i%2==1)
right++;
String str = lengthOfPalindrome(s,left,right);
if(maxLen<str.length())
{
maxLen = str.length();
res = str;
}
}
return res;
}
private String lengthOfPalindrome(String s, int left, int right)
{
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right))
{
left--;
right++;
}
return s.substring(left+1,right);
}
另外有O(n)的算法 manacher算法 http://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html
股票交易
121. Best Time to Buy and Sell Stock
思路：股票交易，买卖一次。可以记录当前的前最小值，dp[i] = max(dp[i-1],s[i] - mins)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int d2 = 0;
if(prices.size() < 2){
return 0;
}
int mins = prices[0];
for(int i = 1; i < prices.size(); i++){
d2 = max(d2, prices[i] - mins);
mins = min(mins, prices[i]);
}
return d2;
}
};
123 Best time to buy and Sell Stock III
思路： 上题的改进版，可以用r[n], l[n] 存 从0-i 和从i-n-1的最大利益交易
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n < 2){
return 0;
}
int r[n] = {0};
int l[n] = {0};
int mins = prices[0];
int maxs = prices[n - 1];
for(int i = 1; i < n; i++){
l[i] = max(l[i-1], prices[i] - mins);
mins = min(prices[i], mins);
}
for(int i = n - 2; i >= 0; i--){
r[i] = max(r[i + 1], maxs - prices[i]);
maxs = max(prices[i], maxs);
}
maxs = r[0];
for(int i = 1; i < n; i++){
maxs = max(maxs, r[i] +l[i]);
}
return maxs;
}
};
另外的一个变形： 可以交易任意次：贪心，只要后边比前一个大就可以交易。
188. Best Time to Buy and Sell Stock IV
最多交易K次 求最大利润 １．第ｉ次买操作买下当前股票之后剩下的最大利润为第(i-1)次卖掉股票之后的利润－当前的股票价格．状态转移方程为：
buy[i] = max(sell[i-1]- curPrice, buy[i]);
２．第ｉ次卖操作卖掉当前股票之后剩下的最大利润为第ｉ次买操作之后剩下的利润＋当前股票价格．状态转移方程为：
sell[i] = max(buy[i]+curPrice, sell[i]);
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size() ==0) return 0;
int len = prices.size(), ans =0;
if(k >= len/2)
{
for(int i = 1; i < len; i++)
if(( prices[i]-prices[i-1] )>0){
ans += prices[i]-prices[i-1];
}
return ans;
}
vector<int> buy(len+1, INT_MIN), sell(len+1, 0);
for(auto val: prices)
{
for(int i =1; i <= k; i++)
{
buy[i] = max(sell[i-1]-val, buy[i]);
sell[i] = max(buy[i]+val, sell[i]);
}
}
return sell[k];
}
};
数组
- 最长上升子序列
- 最长公共子序列 LCS
- 最大连续子序列和
300 最长上升子序列， 可以不连续
思路：用dp[i] 记录包含i元素的最长上升子序列长度。最后要遍历一遍dp数组 求最大的长度。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n < 1){
return 0;
}
int dp[n];
dp[0] = 1;
for(int i = 1; i < n; i++){
int maxs = 1;
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
if((dp[j] + 1) > maxs){
maxs = dp[j] + 1;
}
}
}
dp[i] = maxs;
}
int maxs = dp[0];
for(int i = 1; i < n; i++){
if(maxs < dp[i]){
maxs = dp[i];
}
}
return maxs;
}
};
另外的二分查找法：参见http://www.cnblogs.com/grandyang/p/4938187.html
1.最大连续子序列之和
思路: 和上题类似，用dp[i]表示当前元素在内的最大和。 sum[i] = max(sum[i-1] + arr[i], arr[i])
2 最长公共子序列和最长公共子串
子序列：不用连续，只要是按顺序的序列就行 和编辑距离的求法相似
c[i,j] = 0 (i=0 or j = 0)
c[i,j] = c[i-1,j-1] (s[i]= s[j])
c[i,j] = max(c[i-1,j], c[i][j-1]) (s[i]!= s[j])
子串：必须是连续的
用c[i][j]代表是以s[i]和s[j]结尾的公共子串长度。当str1[i] == str2[j]时，子序列长度veca[i][j] = veca[i - 1][j - 1] + 1；只是当str1[i] ！= str2[j]时，veca[i][j]长度要为0，而不是max{veca[i - 1][j], veca[i][j - 1]}。 而且最后的最长长度是veca二维数组中最长的元素并不是子序列中的最后一个。二者递推式的代表的状态不同。
