## Algorithm Problem: Longest Non-Descending Sub Array or Logest Increasing Subarray, Dynamic programming

The ordinary dynamic programing gives our an algorithm of time complexity O(n2).
However, we could achieve the result by O(n * logn).
Inorder to do this, we need an array named min4length to hold the minimum value in array for the last number of the subarray in each length we could get. For example, given array {1,2,0}, the first run min4len = {1}, second {1,2}, third {0,2}.
At each step i from 0 to array.size() – 1, we find out the position l in min4length that satisfy that min4len[l] > array[i], and all the values before l is small than array[i], if exists. that is min4len[j] < array[i],j < l.
This step we could do in O(log n) time by binary search.
Then if the l is equal to min4len.size(), that indicated that we get to new length record, just push the value array[i] into min4len.
Else, update the min4len[l] = array[i], if min4len[l] > array[i]. And this step will NOT break the non-decreasing attribute of the array min4len, so we could do binary search again.
At last, the min4len.size() is the max length we could achieve.

If we need to output all the values in the final sub-array, it’s much harder, we have to keep track for each length of sub-array. see the code below in function:longestNonDecreasingSubArray()

Problem
Given an array with integers, find the longest non-descending sub-array of the given array.
For example:
Given: {1,2,3,-1,0,1,2,3,4,-1}
Should find out: {-1,0,1,2,3,4} of length 6.

Codes

<

pre>
//
// main.cpp
// LongestIncreasingSubarray
//
// Created by Qiu Xiangyu on 12-12-23.
//

# include

using namespace std;

void printArray(vector array) {
for (size_t i = 0; i < array.size(); ++i) {
if (i > 0) {
cout<<“,”;
}
cout<<array[i];
}
cout<<endl;
}

int lengthOfLongestNonDecreasingSubArray(vector &array) {
if (array.size() == 0) {
return 0;
}
vector min4Length;
for (int i = 0; i < array.size(); ++i) {
int l = 0,h = (int)min4Length.size() – 1;
while (l <= h) {
int mid = (l + h) / 2;
if (min4Length[mid] <= array[i]) {
l = mid + 1;
} else {
h = mid – 1;
}
}
if (l == min4Length.size()) {
min4Length.push_back(array[i]);
} else {
if (min4Length[l] > array[i]) {
min4Length[l] = array[i];
}
}
printArray(min4Length);
}

`return (int)min4Length.size();`

}

vector longestNonDecreasingSubArray(vector &array) {
vector ret;
if (array.size() == 0) {
return ret;
}
vector min4Length;
vector<vector > pathes;
for (int i = 0; i < array.size(); ++i) {
int l = 0,h = (int)min4Length.size() – 1;
while (l <= h) {
int mid = (l + h) / 2;
if (min4Length[mid] <= array[i]) {
l = mid + 1;
} else {
h = mid – 1;
}
}
cout<<“step “<<i<<“, value “<<array[i]<<“, position “<<l<<“, in min4len: “;
printArray(min4Length);
if (l == min4Length.size()) {
min4Length.push_back(array[i]);
vector path;
if (l > 0) {
vector &prePath = pathes[l – 1];
for (int k = 0; k < prePath.size(); ++k) {
path.push_back(prePath[k]);
}
}
path.push_back(i);
pathes.push_back(path);
cout<<“new length, min4len: “;
printArray(min4Length);
cout<<” path: “;
printArray(path);
} else {
if (min4Length[l] > array[i]) {
min4Length[l] = array[i];
if (l > 0) {
vector &prePath = pathes[l – 1];
for (int k = 0; k < prePath.size(); ++k) {
pathes[l][k] = prePath[k];
}
}
pathes[l].back() = i;
cout<<“path for “<<l<<” is:”;
printArray(pathes[l]);
}
cout<<“old for length: “< &lpath = pathes.back();
for (int i = 0; i < lpath.size(); ++i) {
ret.push_back(array[lpath[i]]);
}
return ret;
}

int main(int argc, const char * argv[])
{
vector arr = {1,2,3,-1,0,1,2,3,4,-1};
// int longest = lengthOfLongestNonDecreasingSubArray(arr);
// cout<<longest<<endl;
vector larr = longestNonDecreasingSubArray(arr);
printArray(larr);
cout<<“length : “<<larr.size()<<endl;
return 0;
}

## Algorithm Problem: Coins,Integer Bag Problem using Dynamic Programming

We can calculate the result by dynamic programming.

When there is only one coin valued 1, there is only one way to sum up to the money.
How about the coin valued 2 is available ? We can use the coin2 by count of 0,1,…,Sum/2, and using coin1 for the rest of money which is already calculated by the former step.
Generally, when we already calculated the ways with using the first k types of coins for the money 0,1,…,Sum. When the k+1 types of coin is available, the ways for a certain sum of money tSum is the sum ways of using 0 of new coins, 1 of new coins, 2 of new coins,… and handle the rest of money by first k types of coins, while the rest of money is none-negative.

Then we can get the code below.

Coins or Bags
There are some coins valued 1,2,5,20,50,100. Given a sum of money Sum, how many ways are there by using these coins to sum up to the given money.
The classic integer bag problem is similar to this problem.

Codes:Recur version and Dynamic version

<

pre>

//
// main.cpp
// 背包问题
//
// Created by Qiu Xiangyu on 12-12-15.
//

// 类似背包问题
// 有一些面值的硬币，1 2 5 20 50 100，要求给出凑足某个数目的钱，总共多少方法

# include

using namespace std;

static const int types = 6;
const int coins[types] = {1,2,5,20,50,100};
int waysRecur(int total, int maxAllowType) {
if (maxAllowType <= 0) {
return 1;
}
int maxCoin = coins[maxAllowType];
int ways = 0;
for (int i = 0; i <= total / maxCoin; ++i) {
ways += waysRecur(total – i * maxCoin, maxAllowType – 1);
}
return ways;
}

int waysDp(int sum) {
if (sum <= 0) {
return 1;
}
//1.build a 2-d array to hold the results
int * ways[types];
for (int it = 0 ; it < types; ++it) {
ways[it] = new int[sum + 1];
}
for (int is = 0; is <= sum; ++is) {
ways[0][is] = 1;
}
//2.dp from types 1 to types – 1 to calculate the ways
for (int it = 1; it < types; ++it) {
int coinValue = coins[it];
for (int is = 0; is <= sum; ++is) {
ways[it][is] = 0;
for (int itime = 0; itime * coinValue <= is; ++itime) {
int remain = is – itime * coinValue;
ways[it][is] += ways[it-1][remain];
}
}
}
//3.return the result
int ret = ways[types – 1][sum];
for (int it = 0 ; it < types; ++it) {
delete ways[it];
}
return ret;
}

int main(int argc, const char * argv[])
{
int total = 111;
int ways = waysRecur(total, types – 1);
int wdp = waysDp(total);
cout<<“ways from recur:”<<ways<<endl;
cout<<“ways from dp:”<<wdp<<endl;
return 0;

```/*
5:{1,1,1,1,1},{1,1,1,2},{1,2,2},{5}
it=0:{1,1,1,1,1}
it=1:{1,1,2,2,3}
it=2:{1,1,2,2,4}
*/```

}

## LeetCode题目：Best Time to Buy and Sell Stock III，一维动态规划

Best Time to Buy and Sell Stock III
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 two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

```class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(prices.size() <= 1)
return 0;

//stores the max profit in [0, ... , i] subarray in prices
vector maxEndWith;
{//build the maxEndWith.
int lowest = prices[0];
int maxprofit = 0;
maxEndWith.push_back(0);
for(int i = 1; i < prices.size(); ++i) {
int profit = prices[i] - lowest;
if(profit > maxprofit) {
maxprofit = profit;
}
maxEndWith.push_back(maxprofit);
if(prices[i] < lowest) lowest = prices[i];
}
}

int ret = maxEndWith[prices.size() - 1];
{//reverse to see what is the maxprofit of [i, ... , n-1] subarray in prices
//and meanwhile calculate the final result
int highest = prices[prices.size() - 1];
int maxprofit = 0;
for(int i = prices.size() - 2; i >= 0; --i) {
int profit = highest - prices[i];
if(profit > maxprofit)  maxprofit = profit;
int finalprofit = maxprofit + maxEndWith[i];
if(finalprofit > ret) ret = finalprofit;
if(prices[i] > highest) highest = prices[i];
}
}

return ret;
}
};
```

## LeetCode题目：Unique Paths II，二维动态规划

Unique Paths II
Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.

``` [
[0,0,0],
[0,1,0],
[0,0,0]
]
```

The total number of unique paths is 2.
Note: m and n will be at most 100.

```class Solution {
public:
int uniquePathsWithObstacles(vector > &obstacleGrid) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = obstacleGrid.size();
if(rows == 0) return 0;
int cols = obstacleGrid[0].size();
if(cols == 0) return 0;
int *preways = new int[cols];
int *ways = new int[cols];

//first row
preways[0] = 1 - obstacleGrid[0][0];
for(int i = 1; i  &rowobs = obstacleGrid[ir];
for(int ic = 0; ic < cols; ++ic) {
if(rowobs[ic] == 1) {
ways[ic] = 0;
continue;
}
//from cell above
ways[ic] = preways[ic];
//from left
if(ic > 0) {
ways[ic] += ways[ic - 1];
}
}
int *temp = preways;
preways = ways;
ways = temp;
}
return preways[cols-1];
}
};
```

## LeetCode题目：Unique Binary Search Trees，一维动态规划

Sigma(左边的子树可能状态 * 右边子树可能状态) = 当前个数的nodes形成的BST总数。

Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.

```   1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
```

```class Solution {
public:
int numTrees(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 1) return n;
//ways[i] rep. the number of ways with i nodes
int *ways = new int[n + 1];
ways[0] = 1;
ways[1] = 1;
for(int i = 2 ; i <= n; ++i) {
ways[i] = 0;
for(int left = 0; left < i; ++ left) {
//with number of left noeds in the left sub-tree
int lways = ways[left];
int rways = ways[i - left - 1];
ways[i] += lways * rways;
}
}
int ret = ways[n];
delete [] ways;
return ret;
}
};
```

## LeetCode题目：Triangle，动态规划

Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

```[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
```

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

```class Solution {
public:
int minimumTotal(vector > &triangle) {
int rows = triangle.size();
if(0 == rows) return 0;
int *minSums = new int[rows];
int *temp = new int[rows];

for(int r = 0; r < rows; ++r) {
vector trow = triangle[r];
if(trow.size() != r + 1) return 0;//input error occur
//first should be last 0 add trow[0]
temp[0] = trow[0] + (r > 0 ? minSums[0] : 0);
//from 1 to r - 1, the min from above to parants add self
for(int i = 1; i < r; ++ i) {
temp[i] = trow[i] + min(minSums[i-1],minSums[i]);
}
//last element, just like the first one. only can add self to the last element above.
if(r > 0)
temp[r] = trow[r] + minSums[r-1];
//swap temp with minSums
int *tswap = temp;
temp = minSums;
minSums = tswap;
}

//scan the minSums, find out the minimum one
int m = minSums[0];
for(int i = 1; i < rows; ++i) {
if(minSums[i] < m)
m = minSums[i];
}

delete temp;
delete minSums;
return m;
}
};
```

Code rewrite at 2012-12-30

```class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int levels = triangle.size();
if(levels<=0) return 0;
vector *psum = new vector(levels,0);
vector *psumtemp = new vector(levels,0);
(*psum)[0] = triangle[0][0];
for(int ilevel = 1; ilevel < levels; ++ilevel) {
vector &level = triangle[ilevel];
const int levelsize = level.size();
//only one path could arrive to the first and last number in a level
(*psumtemp)[0] = (*psum)[0] + level[0];
//if (level.size() > 1)
(*psumtemp)[levelsize - 1] = (*psum)[levelsize - 2] + level[levelsize - 1];
//there are 2 pathes for the middle numbers.
for(int ipos = 1; ipos < levelsize - 1; ++ipos) {
int tsum = (*psum)[ipos] + level[ipos];
if(tsum > (*psum)[ipos-1] + level[ipos]) {
tsum = (*psum)[ipos-1] + level[ipos];
}
(*psumtemp)[ipos] = tsum;
}
//swap the psum and psumtemp
vector *ptemp = psum;
psum = psumtemp;
psumtemp = ptemp;
}
//scan the psum and output the minnimum sum
int minsum = (*psum)[0];
for(int i = 1; i < levels; ++i) {
if(minsum > (*psum)[i])
minsum = (*psum)[i];
}
//clearup
delete psum;
delete psumtemp;
return minsum;
}
};
```

Code rewrite at 2013-1-17

```class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = triangle.size();
if(0 == rows) return 0;//error
int *sumrow = new int[rows];
int *sumrowtemp = new int [rows];
sumrow[0] = triangle[0][0];
for(int ir = 1; ir < rows; ++ir) {
vector &trirow = triangle[ir];
sumrowtemp[0] = sumrow[0] + trirow[0];
for(int ic = 1; ic < trirow.size(); ++ic) {
int minsum = sumrow[ic-1];
if(ic < trirow.size()-1 && sumrow[ic] < minsum) {
minsum = sumrow[ic];
}
sumrowtemp[ic] = minsum + trirow[ic];
}
int *temp = sumrow;
sumrow = sumrowtemp;
sumrowtemp = temp;
}
int ret = sumrow[0];
for(int ic = 1; ic < rows; ++ic) {
if(ret > sumrow[ic]) ret = sumrow[ic];
}
delete sumrow;
delete sumrowtemp;
return ret;
}
};
```

## LeetCode题目：Scramble String，三维动态规划

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = “great”:

```    great
/    \
gr    eat
/ \    /  \
g   r  e   at
/ \
a   t
```

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

```    rgeat
/    \
rg    eat
/ \    /  \
r   g  e   at
/ \
a   t
```

We say that “rgeat” is a scrambled string of “great”.
Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

```    rgtae
/    \
rg    tae
/ \    /  \
r   g  ta  e
/ \
t   a
```

We say that “rgtae” is a scrambled string of “great”.
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

```    bool isScrambleDP(string s1, string s2) {
if(s1.size() != s2.size()) return false;
if(s1.size() == 0) return true;
if(s1 == s2) return true;
bool ***iss = NULL;//iss[len][startIndexAtS1][startIndexAtS2]
iss = new bool**[s1.size()];
for(int len = 1;len <= s1.size(); ++len) {
//size at this level
int levelSize = s1.size() - len + 1;
int levelIndex = len - 1;
iss[levelIndex] = new bool*[levelSize];
for(int indexS1 = 0;indexS1 < levelSize; ++ indexS1) {
iss[levelIndex][indexS1] = new bool[levelSize];
for(int is2 = 0; is2 < levelSize; ++is2) {
if(len == 1) {
iss[levelIndex][indexS1][is2] = (s1[indexS1] == s2[is2]);
} else {
iss[levelIndex][indexS1][is2] = false;
for(int seglen1 = 1; seglen1 < len; ++seglen1) {
int seglen2 = len - seglen1;
int sli1 = seglen1 - 1;
int sli2 = seglen2 - 1;
if(iss[sli1][indexS1][is2] && iss[sli2][indexS1 + seglen1][is2 + seglen1]) {
iss[levelIndex][indexS1][is2] = true;
break;
}
if(iss[sli1][indexS1][is2 + seglen2] && iss[sli2][indexS1 + seglen1][is2]) {
iss[levelIndex][indexS1][is2] = true;
break;
}
}
}
}
}
}
return iss[s1.size() - 1][0][0];
}
```

```class Solution {
public:
bool isScramble(string s1, string s2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s1.size() != s2.size()) return false;
if(s1 == s2) return true;
for(int isep = 1; isep < s1.size(); ++ isep) {
//seporate s1 as [0,isep - 1],[isep, s1.size() - 1]
string seg11 = s1.substr(0,isep);
string seg12 = s1.substr(isep);
{//see if forward order is ok
string seg21 = s2.substr(0,isep);
string seg22 = s2.substr(isep);
if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
}
{//see if reverse order is ok
string seg21 = s2.substr(s2.size() - isep);
string seg22 = s2.substr(0,s2.size() - isep);
if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
}
}
return false;
}
};
```

Recursive code rewrite at 2013-2-5, 48ms pass large set

```class Solution {
public:
bool isScramble(string s1, string s2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s1.size() != s2.size()) return false;
if(s1 == s2) return true;
string ts1 = s1,ts2 = s2;
sort(ts1.begin(), ts1.end());
sort(ts2.begin(), ts2.end());
if(ts1 != ts2) return false;
for(int isep = 1; isep < s1.size(); ++ isep) {
//seporate s1 as [0,isep - 1],[isep, s1.size() - 1]
string seg11 = s1.substr(0,isep);
string seg12 = s1.substr(isep);
{//see if forward order is ok
string seg21 = s2.substr(0,isep);
string seg22 = s2.substr(isep);
if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
}
{//see if reverse order is ok
string seg21 = s2.substr(s2.size() - isep);
string seg22 = s2.substr(0,s2.size() - isep);
if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
}
}
return false;
}
};
```

## LeetCode题目：Longest Palindromic Substring，二维动态规划

Updated at 2016-04-28

# Question

Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

# Analyze

The brute force method will take O(n3) time, and apparently, it will exceed the time limit.

To reduce the time, as we noticed there are a lot of duplicated comparisons in the brute force method, the first thought is dynamic programming. But I was too aggressive at the begging, want to solve this with 1-D dynamic programming in O(n) time.

After find out several exceptional cases with either focus on the start of substring or the end of substring, I realized that it can not fit into a 1-D dynamic programming. But 2-D, can easily beat this question.

## 2-D Dynamic Programming

Let’s focus on the start index `si` and end index `ei` of the substring. When we want answer the question: “Is the substring s[si..ei] palindromic?”, we just check if s[si + 1 .. ei – 1] is palindromic and if s[si] == s[ei]. If both conditions are true, then we can get the positive answer. Then if we solve the problem in this order:

```for(int ei = 0; ei < s.length(); ei ++)
for(int si = ei; si >= 0; si --)
{ // implement here }
```

Then we can make sure when we resolve sub problem on (si, ei), we know the answer of (si+1, ei-1). So, just build a 2-D matrix and we can beat this question in O(n2) time.

## Expand from center

That’s the DP solution. And since it’s O(n2), then there is a more straight forward method with the same time level:
Just at each point in the string S, on the positions of it’s characters like 0,1,2,… or between characters like 0.5, 1.5, … . Then from this position, just expand the substring if it is still palindromic. Then there are O(n) centers and at each center, we need expand O(n) times. Thus, this is also a O(n2) time solution. And simpler.

# Codes

## Ruby version DP

```def longest_palindrome(s)
map = {}
max_si, max_ei, max_length = nil, nil, 0
s.length.times do |ei|
si = ei
while si >= 0 do
if si == ei
map[ei] = { si => true }
else
map[ei][si] = s[ei] == s[si] && (si + 1 >= ei || map[ei - 1][si + 1] == true)
end

len = (ei - si + 1)
if map[ei][si] && len > max_length
max_length = len
max_si = si
max_ei = ei
end

si -= 1
end
end

s[max_si..max_ei]
end
```

## Ruby version expand from center

```def expand(s, center)
li, ri = center.floor, center.ceil
if li == ri
li -= 1
ri += 1
end
left_space = li
right_space = s.length - ri - 1
max_space = [left_space, right_space].min
most_left = li - max_space
while li >= most_left do
if s[li] == s[ri]
li -= 1
ri += 1
else
break
end
end
#p [ri - li - 1, li + 1, ri - 1]
[ri - li - 1, li + 1, ri - 1]
end

def longest_palindrome(s)
i = 0
max_si, max_ei, max_len = nil, nil, 0
while i <= s.length - 1 do
len, si, ei = expand(s, i)
if max_len < len
max_si, max_ei, max_len = si, ei, len
end
i += 0.5
end
s[max_si..max_ei]
end
```

## C++ version DP

```class Solution {
public:
inline void setIsPalindrome(bool * dpmap, int si, int ei, int total_length, bool value) {
*(dpmap + total_length * ei + si) = value;
}
inline bool isPalindrome(bool * dpmap, int si, int ei, int total_length) {
return *(dpmap + total_length * ei + si);
}
string longestPalindrome(string s) {
int total_length = s.length();
int max_len = 0, max_si, max_ei;
bool *dpmap = new bool[total_length * total_length];
for(int ei = 0; ei < total_length; ei++) {
for(int si = ei; si >= 0; si--) {
bool positive =
(si == ei) ||
((s[si] == s[ei]) && ((si == ei - 1) || isPalindrome(dpmap, si + 1, ei - 1, total_length)));
setIsPalindrome(dpmap, si, ei, total_length, positive);
if(positive){
int len = ei - si + 1;
if(max_len < len){
max_len = len;
max_si = si;
max_ei = ei;
}
}
}
}
delete dpmap; dpmap = NULL;
return s.substr(max_si, max_len);
}
};
```

# 旧版，有误，奇怪的是当初竟然通过了测试…

1.在子函数longestCommonSub中，如果先new，在得到最长公共串之后delete申请的空间mat的话，运行到大概第5个test case的时候会报runtime error。
2.在代码段

`if(max <= len)`

```class Solution {
public:
string longestCommonSub(string &sa, string &sb) {
int rows = sa.size() + 1;
int cols = sb.size() + 1;
static int *mat = NULL;
if(NULL == mat) {
mat = new int[1001 * 1001];
}
for(int ir = 0 ; ir < rows; ++ ir) {
for(int ic = 0 ; ic < cols; ++ ic) {
*(mat + ir * cols + ic) = 0;
}
}
int max = 0;
int maxIr;
for(int ir = 1 ; ir < rows; ++ ir) {
char sai = sa[ir - 1];
for(int ic = 1 ; ic < cols; ++ ic) {
if(sai == sb[ic - 1]){
int len = 1 + *(mat + (ir-1) * cols + ic - 1);
*(mat + ir * cols + ic) = len;
if(max <= len) {
max = len;
maxIr = ir;
}
}
}
}
string result;
if(max > 0) {
result = sa.substr(maxIr - max, max);
}
return result;
}
string longestPalindrome(string s) {
string rs = s;
for( int i = 0 ; i < s.size(); ++ i) {
rs[i] = s[s.size() - 1 - i];
}
return longestCommonSub(s,rs);
}
};
```

## LeetCode题目：Jump Game II，一维动态规划，贪心

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

```class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int minstep = 0;
int ldist = 0;
int hdist = 0;
if (n == 1) return 0;
while(ldist <= hdist) {
++minstep;
int lasthdist = hdist;
for(int i = ldist; i <= lasthdist; ++i) {
int possibledist = i + A[i];
if (possibledist >= n-1)
return minstep;
if (possibledist > hdist) {
hdist = possibledist;
}
}
ldist = lasthdist + 1;
}
return 0;
}
};
```

```class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 1)
return 0;
const int noWay = n + 1;
int *jumps = new int[n];
jumps[n-1] = 0;
for(int i = n - 2; i >= 0; -- i) {
int lenJump = A[i];
int minJumps = noWay;
for(int j = i + 1; j <= i + lenJump && j < n; ++ j) {
if(jumps[j] + 1 < minJumps)
minJumps = jumps[j] + 1;
}
jumps[i] = minJumps;
}
return jumps[0];
}
};
```

## LeetCode题目：Jump Game，一维动态规划

`vector`

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

```class Solution {
public:
bool canJump(int A[], int n) {
//if (n > 100) return false;
if (n <= 1)
return true;
//vector canJump(n, false);
bool *canJump = new bool[n];
canJump[n - 1] = true;
for( int i = n - 2; i >= 0; --i ) {
int maxJump = A[i];
for(int j = i + 1; j <= i + maxJump && j < n ; ++j) {
if (canJump[j]) {
canJump[i] = true;
break;
}
}
}
return canJump[0];
}
};
```

```class Solution {
public:
bool canJump(int A[], int n) {
if (n <= 1)
return true;
vector canJump(n, false);
canJump[n - 1] = true;
for( int i = n - 2; i >= 0; --i ) {
int maxJump = A[i];
if (i + maxJump >= n)
maxJump = n - i;
for(int j = i + maxJump; j > i; --j) {
if (canJump[j]) {
canJump[i] = true;
break;
}
}
}
return canJump[0];
}
};
```

## LeetCode题目：Interleaving String，二维动态规划

<br>

`bool isInterleaving(string &s1, int len1, string &s2, int len2, string &s3, int len3);`

```isInterleaving(s1,len1,s2,len2,s3,len3)
=   (s3.lastChar == s1.lastChar) && isInterleaving(s1,len1 - 1,s2,len2,s3,len3 - 1)
||(s3.lastChar == s2.lastChar) && isInterleaving(s1,len1,s2,len2 - 1,s3,len3 - 1)
```

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,
When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
//create indicator
vector > match(s1.size() + 1, vector(s2.size() + 1, false));
//initialization the first row and the first column
match[0][0] = true;
for( int l1 = 1; l1 <= s1.size(); ++ l1 ) {
char c1 = s1[l1 - 1];
char c3 = s3[l1 - 1];
if (c1 == c3) {
match[l1][0] = true;
} else
break;
}
for( int l2 = 1; l2 <= s2.size(); ++ l2 ) {
char c2 = s2[l2 - 1];
char c3 = s3[l2 - 1];
if (c2 == c3) {
match[0][l2] = true;
} else
break;
}
//work through the rest of matrix using the formula
for( int l1 = 1; l1 <= s1.size(); ++ l1 ) {
char c1 = s1[l1 - 1];
for( int l2 = 1 ; l2 <= s2.size() ; ++ l2 ) {
char c2 = s2[l2 - 1];
int l3 = l1 + l2;
char c3 = s3[l3 - 1];
if (c1 == c3) {
match[l1][l2] = match[l1 - 1][l2] || match[l1][l2];
}
if (c2 == c3) {
match[l1][l2] = match[l1][l2 - 1] || match[l1][l2];
}
}
}
//the last element is the result
return match[s1.size()][s2.size()];
}
};
```

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
int i1 = 0;
int i2 = 0;
for(int i3 = 0 ; i3 < s3.size(); ++i3) {
if(i1 < s1.size() && s1[i1] == s3[i3]) {
++i1;
} else if (i2 < s2.size() && s2[i2] == s3[i3]) {
++i2;
} else
return false;
}
return true;
}
};
```

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
vector visited(s3.size(),false);
int i3 = 0;
for( int i1 = 0; i1 < s1.size() ; ++i1 ) {
bool match = false;
while(i3 < s3.size()) {
if(s3[i3] == s1[i1]) {
visited[i3 ++] = true;
match = true;
break;
}
++i3;
}
if(!match)
return false;
}
i3 = 0;
for( int i2 = 0; i2 < s2.size() ; ++i2 ) {
bool match = false;
while(i3 < s3.size()) {
if (visited[i3]) {
++i3;
continue;
}
if(s3[i3 ++] == s2[i2]) {
match = true;
break;
}
}
if(!match)
return false;
}
return true;
}
};
```

```class Solution {
public:
bool isInterleave(string &s1,int i1, string &s2, int i2, string &s3, int i3) {
if(i1 == s1.size() && i2 == s2.size() && i3 == s3.size())
return true;
bool match = false;
if(i1 < s1.size() && s1[i1] == s3[i3]) {
match = isInterleave(s1, i1 + 1, s2, i2, s3, i3 + 1);
}
if (!match && i2 < s2.size() && s2[i2] == s3[i3]) {
match = isInterleave(s1, i1, s2, i2 + 1, s3, i3 + 1);
}
return match;
}
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
return isInterleave(s1,0,s2,0,s3,0);
}
};
```

## LeetCode题目：Edit Distance，字符串之间的编辑距离，动态规划

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:
a) Insert a character
b) Delete a character
c) Replace a character

一开始考虑的是，只要找到能重用的最大子串不就行了么，比如将字符：
abc变成xxxxxaxxxxxbxxxxxcxxxxx，只要abc都可以重用，就只需要20步。
但是写完了这个方法之后（见下面失败方法1），被一个简单的case击败了：
将ykyyyab变成abxxxxx，
这种情况下，如果利用了最长子串ab的话，编辑距离实际上是10，但是不用的话只需要7。也就是说，最长子串不一定能降低编辑距离。

然后就又想，上面这种失败case的原因在于为了利用最长子串，导致的头尾一删一添，两次操作，还不如只需一次的替换操作。
于是就限制了一下匹配的区间，比如abxxxxx中的b在匹配的时候，只在kyyya这个范围内才有实际作用，超过这个区间再匹配就会造成得不偿失的一删一添两次操作，得不偿失。
于是写完代码，悲剧的是，又发现问题：
sea变成eat，
按这个算法，编辑距离是3，但实际上是2（删s添t）。

最后花了太长时间忍不了了，百度之，发现正确的解出来方法是用二维的dp。
假如我们要将字符串str1变成str2
sstr1(i)是str1的子串，范围[0到i），sstr1(0)是空串
sstr2(j)是str2的子串，同上
d(i,j)表示将sstr1(i)变成sstr2(j)的编辑距离

首先d(0,t),0<=t<=str1.size()和d(k,0)是很显然的。 当我们要计算d(i,j)时，即计算sstr1(i)到sstr2(j)之间的编辑距离, 此时，设sstr1(i)形式是somestr1c；sstr2(i)形如somestr2d的话， 将somestr1变成somestr2的编辑距离已知是d(i-1,j-1) 将somestr1c变成somestr2的编辑距离已知是d(i,j-1) 将somestr1变成somestr2d的编辑距离已知是d(i-1,j) 那么利用这三个变量，就可以递推出d(i,j)了： 如果c==d，显然编辑距离和d(i-1,j-1)是一样的 如果c!=d，情况稍微复杂一点，

1. 如果将c替换成d，编辑距离是somestr1变成somestr2的编辑距离 + 1，也就是d(i-1,j-1) + 1
2. 如果在c后面添加一个字d，编辑距离就应该是somestr1c变成somestr2的编辑距离 + 1，也就是d(i,j-1) + 1
3. 如果将c删除了，那就是要将somestr1编辑成somestr2d，距离就是d(i-1,j) + 1
4. 那最后只需要看着三种谁最小，就采用对应的编辑方案了。

递推公式出来了，程序也就出来了。

```class Solution {
public:
int minDistance(string word1, string word2) {
int rows = word1.size() + 1;
int cols = word2.size() + 1;
int ** d = (int**)malloc(rows * sizeof(int*));
for(int i = 0; i < rows; ++i){
d[i] = (int*)malloc(cols * sizeof(int));
d[i][0] = i;//sub string in word1 range [0,i) edit to ""
}
for(int j = 0; j < cols; ++j)
d[0][j] = j;//sub string in word2 range [0,j) edit to ""
for(int i = 1; i < rows; ++i) {
char ci = word1[i-1];
for(int j = 1; j < cols; ++j) {
char cj = word2[j-1];
//we will edit str1:word1[0,i) to str2:word2[0,j)
if (ci == cj) {
//if ci equal to cj, then the edit ditance of word1[0,i) to word2[0,j)
// is the same as word1[0,i-1) to word2[0,j-1)
d[i][j] = d[i-1][j-1];
} else {
//if we modify letter ci to cj, there will be 1 operation
int dEdit = d[i-1][j-1] + 1;
//if we add cj to the end of word1[0,i), then from the edit distance of
// word1[0,i) to word2[0, j -1), we can conclude follow dist
int dAdd = d[i][j-1] + 1;
//if we delete ci from word1[0,i), and we know the dist
// from word1[0,i-1) to word2[0,j), the things done:
int dDel = d[i-1][j] + 1;
//the minimum one will be the final distance for str1 to str2
int min = dEdit < dAdd ? dEdit : dAdd;
min = min < dDel ? min : dDel;
d[i][j] = min;
}
}
}
int result = d[rows - 1][cols - 1];
//delete dist;
return result;
}
};
```

1. 通过寻找最长公共子序列（可间断序列）来解决
```class Solution {
public:
class datum{
public:
int lastIndex;
int len;
datum(){
lastIndex = -1;
len = 0;
}
};
inline int locationOfCharInStr(char c, string &str, int startIndex) {
for( int i = startIndex; i < str.size() ; ++ i ) {
if (c == str[i])
return i;
}
return -1;
}
int longestCommonArray(string &str1, string &str2) {
if(str1.size() == 0 || 0 == str2.size())
return 0;
vector maxLen(str1.size());
for( int i = 0; i <  str1.size(); ++i ) {
char ci = str1[i];
datum &di = maxLen[i];
for (int pre = 0 ; pre < i; ++pre ) {
datum dpre = maxLen[pre];
if (dpre.len == 0 ) continue;
int cie = locationOfCharInStr(ci,str2,dpre.lastIndex + 1);
if( cie != -1 && di.len < dpre.len + 1 ) {
di.len = dpre.len + 1;
di.lastIndex = cie;
}
}
if(di.len == 0) {
int cie = locationOfCharInStr(ci,str2,0);
if( cie != -1 ) {
di.len = 1;
di.lastIndex = cie;
}
}
}
int maxlen = 0;
for(int i = 0 ; i < maxLen.size(); ++i) {
if (maxlen < maxLen[i].len)
maxlen = maxLen[i].len;
}
return maxlen;
}
int minDistance(string word1, string word2) {
int lcsl = longestCommonArray(word1,word2);
int maxlen = word1.size();
if(maxlen < word2.size())
maxlen = word2.size();
return maxlen - lcsl;
}
};
```
2. 通过限制查找范围来解决
```class Solution {
public:
class datum{
public:
int loc;
int len;
datum(){
loc = -1;
len = 0;
}
};
inline int locationOfCharInStr(char c, string &str, int startIndex, int endIndex) {
if(endIndex > str.size() - 1)
endIndex = str.size() - 1;
for( int i = startIndex; i <= endIndex ; ++ i ) {
if (c == str[i])
return i;
}
return -1;
}
int minDist(string &str1, string &str2) {
vector minLen(str2.size());
for( int i = 0; i <  str2.size(); ++i ) {
char ci = str2[i];
datum &di = minLen[i];
di.len = str1.size();
di.loc = i;
int endIndex = str1.size() - str2.size() + i;
for (int pre = 0 ; pre < i; ++pre ) {
datum dpre = minLen[pre];
int startIndex = dpre.loc + i - pre;
int cie = locationOfCharInStr(ci,str1,startIndex,endIndex);
if( cie != -1 && (di.len >= dpre.len ||
di.loc > cie)) {
di.len = dpre.len - 1;
di.loc = cie;
}
}
if(di.len == str1.size()) {
int cie = locationOfCharInStr(ci,str1,i,endIndex);
if( cie != -1 ) {
di.len = str1.size() - 1;
di.loc = cie;
}
}
}
int result = str1.size();
for(int i = 0 ; i < minLen.size(); ++i) {
if (result > minLen[i].len)
result = minLen[i].len;
}
return result;
}
int minDistance(string word1, string word2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
string *pSLen, *pSShort;
if(word1.size() >= word2.size()){
pSLen = &word1;
pSShort = &word2;
} else {
pSLen = &word2;
pSShort = &word1;
}
if (pSShort->size() <= 0)
return pSLen->size();
int result = minDist(*pSLen,*pSShort);
return result;
}
};
```

Code rewrite at 2012-12-29

```//
//  main.cpp
//  EditDistance
//
//  Created by Qiu Xiangyu on 12-12-29.
//

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int editDist(string &str0, string &str1) {
if (str0.size() == 0) {
return (int)str1.size();
} else if (str1.size() == 0) {
return (int)str0.size();
}
vector<vector<int> > dists(str0.size() + 1, vector<int>(str1.size() + 1,0));
for(int i0 = 0; i0 <= str0.size(); ++ i0) {
dists[i0][0] = i0;
}
for (int i1 = 0; i1 <= str1.size(); ++i1) {
dists[0][i1] = i1;
}
for (int l0 = 1; l0 <= str0.size(); ++l0) {
for (int l1 = 1; l1 <= str1.size(); ++l1) {
if (str0[l0 - 1] == str1[l1-1]) {
//the same ending of this length pair for strings
dists[l0][l1] = dists[l0-1][l1-1];
} else {
//for replace
int replaceDist = dists[l0-1][l1-1] + 1;
int mindist = replaceDist;
//insert the last char into substr1
int insertDist = dists[l0][l1-1] + 1;
if (mindist > insertDist) {
mindist = insertDist;
}
//delete the last char from substr1
int deleteDist = dists[l0-1][l1] + 1;
if (mindist > deleteDist) {
mindist = deleteDist;
}
dists[l0][l1] = mindist;
}
}
}
return dists[str0.size()][str1.size()];
}

int main(int argc, const char * argv[])
{
string str0 = "abc";
string str1 = "bcd";
int editdist = editDist(str0, str1);
cout<<"edit distance is : "<<editdist<<endl;
return 0;
}

```

Code rewrite 2012-12-30

```class Solution {
public:
int minDistance(string word1, string word2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > dists(word1.size() + 1, vector(word2.size() + 1, 0));
for(int l1 = 1; l1 <= word1.size(); ++l1) {
//by adding chars in sub-word1 to sub-word2 with zero length
dists[l1][0] = l1;
}
for(int l2 = 1; l2 <= word2.size(); ++l2) {
dists[0][l2] = l2;
}
for(int l1 = 1; l1 <= word1.size(); ++l1) {
for(int l2 = 1; l2 <= word2.size(); ++l2) {
if(word1[l1-1] == word2[l2-1]) {
dists[l1][l2] = dists[l1-1][l2-1];
} else {
//if we can form sub-word1 with length l1-1 to sub-word2 with length l2-1,
//with steps of dists[l1-1][l2-1]
//then we can replace the char sub-word2[l2] to sub-word1[l1],
//then we can edit sub-word2 with length l2 to sub-word1 with length l1
//with steps of dists[l1-1][l2-1] + 1
int replacedist = dists[l1-1][l2-1] + 1;
//if we can form sub-word1 with length l1-1 to sub-word2 with length l2,
//with steps of dists[l1-1][l2]
//then we can add the char sub-word1[l1] after sub-word2[l2],
//or se can delete the char sub-word1[l1]
//then we can edit sub-word2 with length l2 to sub-word1 with length l1
//with steps of dists[l1-1][l2] + 1
int adddist = dists[l1-1][l2] + 1;
//or if we can form sub-word1 with length l1 to sub-word2 with length l2-1,
//with steps of dists[l1][l2-1]
//then we can add the char sub-word2[l2] after sub-word1[l1],
//or we can delete the char sub-word2[l2]
//then we can edit sub-word2 with length l2 to sub-word1 with length l1
//with steps of dists[l1][l2-1] + 1
int deldist = dists[l1][l2-1] + 1;

int mindist = replacedist;
if(mindist>deldist) mindist = deldist;
dists[l1][l2] = mindist;
}
}
}
return dists[word1.size()][word2.size()];
}
};
```

## LeetCode题目：Decode Ways，一维动态规划

Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).
The number of ways decoding “12” is 2.

```class Solution {
public:
int numDecodings(string s) {
if(s.size() == 0)
return 0;
if(s.size() == 1 && s[0] != '0')
return 1;
if(s[0] == '0')
return 0;
int fix = s.size() == 2 ? 1: 0;
if(s[0] == '1' || (s[0] == '2' && s[1] <= '6'))
return numDecodings(s.substr(1)) + numDecodings(s.substr(2)) + fix;
return numDecodings(s.substr(1));
}
};
```

```class Solution {
public:
int numDecodings(string s) {
if(s.size() == 0)
return 0;
vector ways(s.size() + 2,1);//多出来的两个作为占位符，避免程序内判断是否超过size
for(int i = s.size() - 1; i >= 0; --i)
{
//self
if(s[i] == '0')
ways[i] = 0;
else
ways[i] = ways[i+1];

//self and next
if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
ways[i] += ways[i + 2];
}
}
return ways[0];
}
};
```

Code rewrite at 2013-1-4, not very nice

```class Solution {
public:
int numDecodings(string s) {
if (s.size() == 0) return 0;
if (s[0] == '0') return 0;
int *ways = new int[s.size()];
ways[0] = 1;
for(int ei = 1; ei < s.size(); ++ei) {
char last = s[ei - 1];
char cur = s[ei];
if(cur == '0') {
if(last == '1' || last == '2')
ways[ei] = ei > 1 ? ways[ei-2] : 1;
else {
delete ways;
return 0;
}
} else if(last == '1' || (last == '2' && cur <= '6')) {
ways[ei] = ways[ei-1];
ways[ei] += ei > 1 ? ways[ei-2] : 1;
} else {
ways[ei] = ways[ei-1];
}
}
int ret = ways[s.size() - 1];
delete ways;
return ret;
}
};
```

## LeetCode题目：Combination Sum II

1. unique和erase的用法
`result.erase(unique(result.begin(),result.end()),result.end());`
2. 细心检查语法

Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

1432ms过大测试集合

```class Solution {
public:
vector > combinationSum2(vector &num, int target) {
if(num.size() == 0)
return vector >();
sort(num.begin(),num.end());
vector > > *pR = new vector > >(target + 1);
vector > > *pT = new vector > >(target + 1);
//initialize
{
int c0 = num[0];
if(c0 > 0 && c0 <= target)
{
vector titem = vector(1,c0);
(*pR)[c0].push_back(titem);
}
}

for(int k = 1; k < num.size(); ++k)
{
int ck = num[k];
for(int t = 1; t <= target; ++t)
{
(*pT)[t].clear();
vector > &excludePre = (*pR)[t];
for( int i = 0 ; i < excludePre.size(); ++i)
{
(*pT)[t].push_back(excludePre[i]);
}
if(t - ck > 0)
{
vector > &includePre = (*pR)[t - ck];
for( int i = 0 ; i < includePre.size(); ++i)
{
vector tResult = includePre[i];
tResult.push_back(ck);
(*pT)[t].push_back(tResult);
}
} else if (t == ck)
{
(*pT)[t].push_back(vector(1,ck));
}
}
vector > > *temp = pR;
pR = pT;
pT = temp;
}
vector > &result = (*pR)[target];
sort(result.begin(),result.end());
result.erase(unique(result.begin(),result.end()),result.end());
return result;
}
};
```

## LeetCode题目：Combination Sum，动态规划

Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

```class Solution {
public:
vector > combinationSum(vector &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (candidates.size() == 0)
return vector >();
sort(candidates.begin(),candidates.end());
vector > > *pR = new vector > >(target + 1);
vector > > *pT = new vector > >(target + 1);
for (int t = 1; t <= target; ++ t)
{
int c = candidates[0];
if (t % c == 0)
{
(*pR)[t].push_back(vector(t/c,c));
}
}
for (int k = 1; k < candidates.size(); ++k)
{
int ck = candidates[k];
for (int t = 1 ; t <= target; ++t)
{
(*pT)[t].clear();
for (int p = 0; p * ck <= t; ++p)
{
int remain = t - ck * p;
if (remain == 0)
{
(*pT)[t].push_back(vector(p,ck));
}
else
{
vector > &rRemain = (*pR)[remain];
for (int irr = 0; irr < rRemain.size() ;++ irr)
{
vector newSum(rRemain[irr]);
for(int ip = 0; ip < p; ++ip)
newSum.push_back(ck);
(*pT)[t].push_back(newSum);
}
}
}
}
vector > > *pTemp = pR;
pR = pT;
pT = pTemp;
}
return (*pR)[target];
}
};
```