- 397. Longest Continuous Increasing Subsequence
- 110. Minimum Path Sum
- 41. Maximum Subarray
- 512. Decode Ways
- 436. Maximal Square
- 200. Longest Palindromic Substring
- 394. Coins in a Line
- 395. Coins in a Line II
- 392. House Robber
- 191. Maximum Product Subarray
- 76. Longest Increasing Subsequence
- 676. Decode Ways II
- 168. Burst Balloons
- 430. Scramble String
- 398. Longest Continuous Increasing Subsequence II
同学们可能对什么使用正序求解，什么时候倒序求解有一点疑问。
我们现在说的是一种bottom-up的方式，每个大问题用子问题去求解，保证每次要用到的子问题都已经先被计算过了，我们也把它叫做递推(recurrence)。
还有一种叫做记忆化搜索（memorization），就是递归得求答案，并把算过的内容存在数组里，因为它是从上往下算的，这是一种top-down的方式。
一般来说动态规划题两种都可以用，但是，有些时候某一种写法能比另一种写法简单很多，所以两种写法都要掌握
397. Longest Continuous Increasing Subsequence
class Solution {public:/*** @param A: An array of Integer* @return: an integer*/int longestIncreasingContinuousSubsequence(vector<int> &A) {// write your code hereif (A.size() == 0){return 0;}int res = 1, temp = 1;bool flag = A[1] - A[0];for (int i = 1; i < A.size(); i ++){if (flag ^ A[i - 1] > A[i]){temp ++;res = max(res, temp);}else{flag = !flag;temp = 2;}}return res;}};
110. Minimum Path Sum
滚动数组写法
class Solution {
public:
/**
* @param grid: a list of lists of integers
* @return: An integer, minimizes the sum of all numbers along its path
*/
int minPathSum(vector<vector<int>> &grid) {
// write your code here
int m = grid.size();
int n = grid[0].size();
//vector<vector<int>> sum (m, vector<int>(n, 0));
int sum[2][n];
sum[0][0] = grid[0][0];
for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j ++){
if (i == 0 && j > 0){
sum[i % 2][j] = sum[i % 2][j - 1] + grid[i][j];
}
if (i > 0 && j == 0){
sum[i % 2][j] = sum[(i - 1) % 2][j] + grid[i][j];
}
if (i > 0 && j > 0){
sum[i % 2][j] = min(sum[(i - 1) % 2][j], sum[i % 2][j - 1]) + grid[i][j];
}
}
}
return sum[(m - 1) % 2][n - 1];
}
};
41. Maximum Subarray
class Solution {
public:
/**
* @param nums: A list of integers
* @return: An integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> &nums) {
// write your code here
int n[2];
if (nums.size() == 0){
return 0;
}
int sum = nums[0];
n[0] = nums[0];
for (int i = 1; i < nums.size();i ++){
if (n[(i - 1) % 2] < 0){
n[i % 2] = nums[i];
}else{
n[i % 2] = n[(i - 1) % 2] + nums[i];
}
sum = max (sum, n[i % 2]);
}
return sum;
}
};
512. Decode Ways
436. Maximal Square
class Solution {
public:
/**
* @param matrix: a matrix of 0 and 1
* @return: an integer
*/
int maxSquare(vector<vector<int>> &matrix) {
int m = matrix.size();
int n = matrix[0].size();
if (m == 0 || n == 0){
return 0;
}
int res = 0;
bool temp[m][n];
for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j ++){
temp[i][j] = matrix[i][j];
if (temp[i][j] == 1){
res = 1;
}
}
}
int minimum = min(m, n);
for (int i = 1; i < minimum; i ++){
bool roundTemp = 0;
for (int j = 0; j < m - i; j ++){
for (int k = 0; k < n - i; k ++){
temp[j][k] = temp[j][k] && temp[j + 1][k] && temp [j][k + 1] && temp[j + 1][k + 1];
if (temp[j][k]){
roundTemp = 1;
}
}
}
if (roundTemp == 1){
res = i + 1;
}else{
break;
}
}
cout << res;
res = res * res;
return res;
}
};
200. Longest Palindromic Substring
class Solution {
public:
/**
* @param s: input string
* @return: the longest palindromic substring
*/
string longestPalindrome(string &s) {
// write your code here
int res = 0;
string result;
for (int i = 0; i < s.size(); i ++){
int start = i, end = i, temp = 1;
while (start > -1 && end < s.size()){
if (s[start] == s[end]){
if (temp > res){
res = temp;
result = s.substr(start, end - start + 1);
}
}else{
break;
}
temp += 2;
start --;
end ++;
}
}
for (int i = 0; i < s.size() - 1; i ++){
int start = i, end = i + 1, temp = 2;
while (start > -1 && end < s.size()){
if (s[start] == s[end]){
if (temp > res){
res = temp;
result = s.substr(start,end - start + 1);
}
}else{
break;
}
temp += 2;
start --;
end ++;
}
}
return result;
}
};
394. Coins in a Line
class Solution {
public:
/**
* @param n: An integer
* @return: A boolean which equals to true if the first player will win
*/
bool firstWillWin(int n) {
// write your code here
vector <bool> res(n + 1);
res[1] = 1;
res[2] = 1;
for (int i = 3; i < n + 1; i ++){
res[i] = !res[i - 1] || !res[i - 2];
}
return res[n];
}
};
395. Coins in a Line II
class Solution {
public:
/**
* @param values: a vector of integers
* @return: a boolean which equals to true if the first player will win
*/
bool firstWillWin(vector<int> &values) {
// write your code here
if (values.size() < 3){
return 1;
}
vector<int> res (values.size());
res[values.size() - 1] = values[values.size() - 1];
res[values.size() - 2] = values[values.size() - 1] + values[values.size() - 2];
for (int i = values.size() - 3; i > -1; i --){
res[i] = max(-res[i + 2] + values[i + 1] + values[i], -res[i + 1] + values[i]);
}
return res[0] > 0;
}
};
392. House Robber
dp[i] = max(dp[i-1], dp[i-2] + A[i-1]) better way
class Solution {
public:
/**
* @param A: An array of non-negative integers
* @return: The maximum amount of money you can rob tonight
*/
long long houseRobber(vector<int> &A) {
// write your code here
if (A.size() == 0){
return 0;
}
vector <long long> res(A.size());
res[0] = A[0];
if (A.size() == 1){
return A[0];
}
res[1] = max(A[0], A[1]);
if (A.size() == 2){
return A[1];
}
res[2] = max(A[0] + A[2], A[1]) ;
for (int i = 3; i < A.size(); i ++){
res[i] = max(res[i - 2], res[i - 3]) + A[i];
}
return max(res[A.size()- 1], res[A.size() - 2]);
}
};
191. Maximum Product Subarray
结果只能是前一个结果的最大值或者最小值乘以下一个数或者下个数本身
class Solution {
public:
/**
* @param nums: An array of integers
* @return: An integer
*/
int maxProduct(vector<int> &nums) {
// write your code here
if (nums.size() == 0) {
return 0;
}
int m = nums.size();
vector <vector<int>> res(m, vector<int>(2));
int result = nums[0];
res[0][0] = nums[0];
res[0][1] = nums[0];
for (int i = 1; i < nums.size(); i++) {
res[i][0] = max(max((res[i - 1][0] * nums[i]), (res[i - 1][1] * nums[i])), nums[i]);
res[i][1] = min(min((res[i - 1][0] * nums[i]), (res[i - 1][1] * nums[i])), nums[i]);
result = max(result, res[i][0]);
}
return result;
}
};
76. Longest Increasing Subsequence
O(n方)
不断更新ranknow
class Solution {
public:
/**
* @param nums: An integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> &nums) {
// write your code here
if (nums.size() == 0){
return 0;
}
int size = nums.size();
vector<int> rankNow(size, 1);
for (int i = 1; i < size; i ++){
int temp = 1;
for (int j = 0; j < i; j ++){
if (nums[j] < nums[i] && rankNow[j] + 1 > temp){
temp = rankNow[j] + 1;
}
}
//cout << temp;
rankNow[i] = temp;
}
auto maxPos = max_element(rankNow.begin(), rankNow.end());
return rankNow[maxPos - rankNow.begin()];
}
};
O（nlogn）
找到lower bound，替换
class Solution {
public:
/**
* @param nums: An integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> &nums) {
// write your code here
if (nums.size() == 0){
return 0;
}
//存每个数为结尾的最长子序列
//vector <int> dp (nums.size());
//存储dp值为i的最小的数字
vector <int> res (nums.size() + 1);
for (int i = 1; i < nums.size() + 1; i ++){
res[i] = INT_MAX;
}
res[1] = 0;
int temp = 1;
for (int i = 0; i < nums.size(); i ++){
int index = binarySearch(nums, res, temp, i);
if (index == temp){
temp ++;
}
res[index] = nums[i];
//cout << index << ' ' << res[index]<< endl;
}
temp = 0;
for (int i = 1; i < nums.size() + 1; i ++){
if (res[i] == INT_MAX){
break;
}
temp ++;
}
return temp;
}
int binarySearch(vector <int> & nums, vector <int> &res, int temp, int i){
int start = 0, end = temp;
while (start + 1 < end){
int mid = start + (end - start) / 2;
if (res[mid] < nums[i]){
start = mid;
}else{
end = mid;
}
}
return end;
}
};
直接用自带函数
class Solution {
public:
/**
* @param nums: An integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> &nums) {
// write your code here
vector<int> res;
if(nums.size()==0){
return 0;
}
res.push_back(nums[0]);
for(int i=1;i<nums.size();i++){
if(nums[i]>res[res.size()-1]){
res.push_back(nums[i]);
}else{
auto it = lower_bound(res.begin(),res.end(),nums[i]);
*it = nums[i];
}
}
return res.size();
}
};
676. Decode Ways II
class Solution {
public:
/**
* @param s: a message being encoded
* @return: an integer
*/
int numDecodings(string &s) {
// write your code here
const int mod = 1000000007;
if (s.size() == 0) {
return 0;
}
vector <long long> res(s.size() + 1);
if (s[0] == '*') {
res[0] = 9;
}
else if (s[0] != '0') {
res[0] = 1;
}
else {
return 0;
}
if (s.size() == 1) {
return res[0];
}
int temp;
//temp = (s[0] - '0') * 10 + (s[1] - '0');
if (s[0] == '*') {
if (s[1] == '*') {
res[1] = 96;
}
else if (s[1] - '0' < 7) {
res[1] = 11;
}
else {
res[1] = 10;
}
}
else if (s[1] == '*') {
if (s[0] - '0' == 0) {
res[1] = 9;
}
else if (s[0] - '0' == 1) {
res[1] = 18;
}
else if (s[0] - '0' == 2) {
res[1] = 15;
}
else {
res[1] = 9;
}
}
else {
temp = (s[0] - '0') * 10 + (s[1] - '0');
if (temp == 10 || temp == 20) {
res[1] = 1;
}
else if (temp > 10 && temp < 27) {
res[1] = 2;
}
else if (temp % 10 == 0) {
res[1] = 0;
}
else {
res[1] = 1;
}
}
if (s.size() == 2) {
return res[1];
}
for (int i = 2; i < s.size(); i++) {
if (s[i - 1] == '*') {
if (s[i] == '*') {
res[i] = (15 * res[i - 2] + 9 * res[i - 1]) % mod;
}
else if (s[i] - '0' < 7) {
res[i] = (2 * res[i - 2] + 1 * res[i - 1]) % mod;
}
else {
res[i] = (1 * res[i - 2] + 1 * res[i - 1]) % mod;
}
}
else if (s[i] == '*') {
if (s[i - 1] - '0' == 0) {
res[i] = (9 * res[i - 1]) % mod;
}
else if (s[i - 1] - '0' == 1) {
res[i] = (9 * res[i - 1] + 9 * res[i - 2]) % mod;
}
else if (s[i - 1] - '0' == 2) {
res[i] = (9 * res[i - 1] + 6 * res[i - 2]) % mod;
}
else {
res[i] = (9 * res[i - 1]) % mod;
}
}
else {
temp = (s[i - 1] - '0') * 10 + (s[i] - '0');
if (temp == 0) {
break;
}
else if (temp == 10 || temp == 20) {
res[i] = res[i - 2];
}
else if (temp > 10 && temp < 27) {
res[i] = (res[i - 1] + res[i - 2]) % mod;
}
else if (temp % 10 == 0) {
res[i] = 0;
}
else {
res[i] = res[i - 1];
}
}
}
return res[s.size() - 1];
}
};
168. Burst Balloons
res[i][j]记录 i到j里面所有气球都被戳破的结果，k是ij中最后一个被戳破的气球
最后写for循环的时候要注意i从nums.size - 2开始一直到0， j从i+2开始·往后涨
class Solution {
public:
/**
* @param nums: A list of integer
* @return: An integer, maximum coins
*/
int maxCoins(vector<int> &nums) {
// write your code here
if (nums.size() == 0){
return 0;
}
int m = nums.size();
vector <int> newNums(m + 2);
newNums[0] = newNums[m + 1] = 1;
for (int i = 1; i < m + 1; i ++){
newNums[i] = nums[i - 1];
//cout << i << ' ' << newNums[i] << endl;
}
int res[m + 2][m + 2];
for (int i =0; i < m + 2; i ++){
res[i][i + 1] = 0;
}
for (int i = m - 1; i >= 0; i --){
for (int j = i + 2; j < m + 2; j ++){
res[i][j] = 0;
for (int k = i + 1; k < j ; k++){
res[i][j] = max(res[i][j], res[i][k] + res[k][j] + newNums[i] * newNums[j] * newNums[k]);
//cout << i << ' ' << j << ' ' << k << ' ' << res[i][j] << endl;
}
}
}
return res[0][m + 1];
}
};
430. Scramble String
使用递归的方法
class Solution {
public:
/**
* @param s1: A string
* @param s2: Another string
* @return: whether s2 is a scrambled string of s1
*/
bool isScramble(string &s1, string &s2) {
// write your code here
int m = s1.size();
int n = s2.size();
if (m != n) {
return false;
}
string str1 = s1, str2 = s2;
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
if (str1 != str2) return false;
if (s1 == s2){
return true;
}
for (int i = 1; i < m; i ++){
string s11 = s1.substr(0, i);
string s12 = s1.substr(i);
string s21 = s2.substr(0, i);
string s22 = s2.substr(i);
if (isScramble(s11, s21) && isScramble(s12, s22)){
return true;
}
s21 = s2.substr(0, m - i);
s22 = s2.substr(m - i);
if (isScramble(s11, s22) && isScramble(s21, s12)){
return true;
}
}
return false;
}
};
398. Longest Continuous Increasing Subsequence II
记忆化搜索，每个点最多遍历4次，总时间复杂度m * n
class Solution {
public:
/**
* @param matrix: A 2D-array of integers
* @return: an integer
*/
int maxx = 0;
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};
int longestContinuousIncreasingSubsequence2(vector<vector<int>> &matrix) {
// write your code here
int m = matrix.size();
if (m == 0){
return 0;
}
int n = matrix[0].size();
vector <vector <int>> posMin (m, vector<int>(n, 0));
for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j ++){
dfs(i, j , posMin, matrix, 1, m, n);
}
}
return maxx;
}
void dfs(int x, int y, vector <vector <int>>& posMin, vector<vector<int>> &matrix, int temp, int m, int n){
//cout << x << ' ' << y << ' ' << temp << endl;
maxx = max(maxx, temp);
for (int i = 0; i < 4; i ++){
int nowX = dx[i] + x;
int nowY = dy[i] + y;
if (nowX >= m || nowX < 0 || nowY >= n || nowY < 0 || matrix[nowX][nowY] <= matrix[x][y]){
continue;
}
if (posMin[nowX][nowY] >= temp + 1){
continue;
}
int newTemp = temp + 1;
posMin[nowX][nowY] = newTemp;
dfs (nowX, nowY, posMin, matrix, newTemp, m, n);
}
}
};
若有收获，就点个赞吧
0 人点赞
