5. 最长回文子串
使用动态规划。
dp[i][j]代表字符串s的第i个字符到第j个字符是否是回文子串，是的话为1，不是的话为0。
边界 ：
dp[i][i] 一定为 1，如果相邻两个字符相等，那么dp[i][i+1] = 1。
转移方程：
判断每三个相邻的字符是否是回文子串，那么只需要判断首尾两个字符是否相等，如果相等，并且中间那个字符是回文子串，那么这三个相邻的字符就是回文子串。
判断每四个相邻的字符是否是回文子串，也只需要判断首尾两个字符是否相等，如果相等，并且中间的两个字符是回文子串，那么这四个相邻的字符就是回文子串。
以此类推，直到求出字符串s是否是回文子串。
在这个遍历的过程中，使用一个变量res用来记录最长回文子串的长度。
知道最长回文子串的长度之后，那么再去找到这个最长回文子串就很容易了。
时间复杂度O(n^2)。
class Solution {
public String longestPalindrome(String s) {
if ("".equals(s)) {
return "";
}
int res = 1;
int len = s.length();
int[][] dp = new int[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
if (i != len - 1 && s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = 1;
res = 2;
}
}
for (int L = 3; L <= len; L++) {
for (int i = 0; i + L - 1 < len; i++) {
int j = i + L - 1;
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1] == 1) {
dp[i][j] = 1;
res = L;
}
}
}
for (int i = 0; i + res - 1 < len; i++) {
if (dp[i][i + res - 1] == 1) {
return s.substring(i, i + res);
}
}
return "";
}
}
10. 正则表达式匹配
递归：
class Solution {
public boolean isMatch(String s, String p) {
if (p.isEmpty()) {
return s.isEmpty();
}
boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
if (p.length() >= 2 && p.charAt(1) == '*') {
return isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p));
} else {
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}
}
动态规划：
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
int sLen = s.length(), pLen = p.length();
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
dp[0][0] = true;
for (int i = 1; i <= pLen; i++) {
if (p.charAt(0) == '*') {
dp[0][1] = false;
continue;
}
if (p.charAt(i - 1) == '*') {
dp[0][i] = dp[0][i - 2];
}
}
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; j++) {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(0) == '*') {
continue;
} else if (p.charAt(j - 1) == '*') {
if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
} else {
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[sLen][pLen];
}
}
32. 最长有效括号
dp[i] 代表字符串前i个字符的最长有效括号的长度。
边界：
dp[0] = 0，只要字符串某个位置i的字符是 '('， 那么dp[i] = 0。
转移方程：
如果s[i] = ')'，如果s[i-1] = '('，那么dp[i] = dp[i-2]+2 。
如果s[i] = ')',如果s[i-1]=')'， 那么得找到能和s[i]匹配的括号的位置，dp[i-1]代表前i-1个最长有效括号的长度，记index = i - dp[i-1] - 1。那么s[index]就是与s[i]进行匹配的括号。如果s[index] = ')' ，那么肯定不匹配，dp[i] = 0。如果s[index] = '('，那么匹配，则dp[i] = dp[i-1] + 2 + dp[index-1]。
class Solution {
public int longestValidParentheses(String s) {
int res = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '(') {
dp[i] = 0;
} else if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
} else if (s.charAt(i - 1) == ')') {
int index = i - dp[i - 1] - 1;
if (index >= 0 && s.charAt(index) == '(') {
dp[i] = dp[i - 1] + (index - 1 >= 0 ? dp[index - 1] : 0) + 2;
} else if (index >= 0 && s.charAt(index) == ')') {
dp[i] = 0;
}
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
更精简：
class Solution {
public int longestValidParentheses(String s) {
int res = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
} else {
int index = i - dp[i - 1] - 1;
if (index >= 0 && s.charAt(index) == '(') {
dp[i] = dp[i - 1] + 2 + (index - 1 >= 0 ? dp[index - 1] : 0);
}
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
44. 通配符匹配
dp[i][j]代表s的前i个字符与p的前j个字符是否匹配，匹配为true，不匹配为false。
边界：
dp[0][0] = true，两个空字符串是匹配的。
只要p中只有*号，那么空字符串s与p是匹配的。
转移方程：
对于dp[i][j]，代表s的前i个字符与p的前j个字符是否匹配。
s的第i个字符是 s[i-1] ，p的第j个字符是p[j-1]。
1.如果p[j-1] = '?' 或者 s[i-1] = p[j-1] 那么 dp[i][j] = dp[i-1][j-1]。
2.如果p[j-1] = ''，那么号可以匹配空字符串，也可以匹配多个字符串。
匹配空字符串的时候，dp[i][j] = dp[i][j-1]。
匹配多个字符串的时候,dp[i][j] = dp[i-1][j]。
综合起来，dp[i][j] = dp[i][j - 1] || dp[i - 1][j]
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length(), pLen = p.length();
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
dp[0][0] = true;
for (int i = 1; i <= pLen; i++) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = true;
} else {
break;
}
}
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; j++) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == s.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[sLen][pLen];
}
}
53. 最大子序和
dp[i]代表以i位置的数为结尾的最大子序和
边界：
dp[0] = nums[0]
转移方程：
dp[i] = max(dp[i-1] + nums[i] , nums[i])
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
res = Math.max(dp[i], res);
}
return res;
}
}
优化：
当dp[i]只与dp[i-1]有关时，使用一个变量pre用来维护对于当前的dp[i]，dp[i-1]是多少。空间复杂度降到O(1)。
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int pre = nums[0];
for (int i = 1; i < nums.length; i++) {
pre = Math.max(nums[i], pre + nums[i]);
res = Math.max(pre, res);
}
return res;
}
}
62. 不同路径
dp[i][j] 代表到第i行第j列的某个格子有多少种不同的路径。
边界：
第一行和第一列的所有格子只有1种路径。
转移方程：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
时间复杂度O(n^2 )，空间复杂度O(n^2)
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
优化：
pre[i]代表到达前一列第i行的路径个数，cur[i]代表到达当前列第i行的路径个数。
初始pre[i] = 1, cur[i] = 1。
class Solution {
public int uniquePaths(int m, int n) {
int[] pre = new int[n];
int[] cur = new int[n];
for (int i = 0; i < n; i++) {
pre[i] = 1;
}
for (int i = 0; i < n; i++) {
cur[i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
cur[j] = cur[j - 1] + pre[j];
}
pre = cur.clone();
}
return pre[n - 1];
}
}
63. 不同路径 II
dp[i][j] 代表到第i行第j列的某个格子有多少种不同的路径。
边界：
第一行和第一列到达障碍物之前的格子都只有一条路径。
转移方程：
当第i行第j列的格子不是障碍物时，dp[i][j] = dp[i-1][j] + dp[i][j-1]。
时间复杂度O(n^2 )，空间复杂度O(n^2)
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 0) {
dp[i][0] = 1;
} else {
break;
}
}
for (int j = 0; j < n; j++) {
if (obstacleGrid[0][j] == 0) {
dp[0][j] = 1;
} else {
break;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
优化：
64. 最小路径和
dp[i][j]代表到达第i行第j列的格子的最小路径
边界：
到达第一列的所有格子的路径只有一条，最小路径和就是所有格子长度的累加。
到达第一行的所有格子的路径只有一条，最小路径和就是所有格子长度的累加。
转移方程：
到达第i行第j列的某个格子的最小路径和为 到达他上面那个格子或左边那个格子的路径和较小者加上他自己的长度。
即 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
时间复杂度On2，空间复杂度On2
class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length, col = grid[0].length;
int[][] dp = new int[row][col];
for (int i = 0; i < row; i++) {
dp[i][0] = (i - 1 >= 0 ? dp[i - 1][0] : 0) + grid[i][0];
}
for (int j = 0; j < col; j++) {
dp[0][j] = (j - 1 >= 0 ? dp[0][j - 1] : 0) + grid[0][j];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][col - 1];
}
}
70. 爬楼梯
dp[i] 代表爬i阶楼梯的方法数
边界：
dp[0] = 1 , dp[1] = 1
转移方程：
dp[i] = dp[i-2] + dp[i-1]
时间复杂度On，空间复杂度On
class Solution {
public int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
优化：
由于dp[i]只与前两个状态有关，可以用滚动数组的思想将空间复杂度降到O1
初始p代表跳0阶，q代表跳1阶，r代表跳1阶。 然后不断滚动更新。
class Solution {
public int climbStairs(int n) {
int p = 1, q = 1, r = 1;
for (int i = 2; i <= n; i++) {
r = p + q;
p = q;
q = r;
}
return r;
}
}
72. 编辑距离
dp[i][j]代表word1的前i个字符与word2前j个字符的编辑距离。
边界：
dp[i][0] = i , dp[0][j] = j
转移方程：
1.如果word1的第i个字符与word2的第j个字符相等，即word1[i-1] = word2[j-1]，那么dp[i][j] = dp[i-1][j-1]。
2.如果word1的第i个字符与word2的第j个字符不相等：
可以把word1插入一个字符使相等，即在word1前i-1个字符转化成word2的前j个字符的基础上，再插入一个字符，此时dp[i][j] = dp[i-1][j] + 1
也可以把word1删除一个字符使相等，等价于word2增加一个字符使相等，即在word1的前i个字符转化成word2的前j-1个字符的基础上，再插入一个字符，此时dp[i][j] = dp[i][j-1] +1
也可以把word1替换一个字符使相等，即word1前i-1个字符转化成word2前j-1个字符的基础上，再替换一个字符，此时dp[i][j] = dp[i-1][j-1] + 1
转移方程取三者情况最小值。
时间复杂度On2，空间复杂度On2。
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length(), len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[len1][len2];
}
}
87. 扰乱字符串
91. 解码方法
dp[i] 代表到字符串索引i为止的字符串的解码方法数。
边界：
若字符串为空或者以0开头，直接返回0 ，否则dp[0] = 1。
转移方程：
- 若s[i] = '0'
若s[i-1] = '1' 或 '2'，则dp[i] = dp[i-2]
若s[i-1] != '1' 或 '2'， 则 return 0 - 若'1' <= s[i] <= '6'
若s[i-1] = '1' 或 '2'，则dp[i] = dp[i-1] + dp[i-2]
若s[i-1] != '1' 或 '2'，则dp[i] = dp[i-1] - 若'7' <= s[i] <= '9'
若s[i-1] = '1' ， 则dp[i] = dp[i-1] + dp[i-2]
若s[i-1] != '1' ，则dp[i] = dp[i-1]
时间复杂度On，空间复杂度On
class Solution {
public int numDecodings(String s) {
if ("".equals(s) || s.charAt(0) == '0') {
return 0;
}
int[] dp = new int[s.length()];
dp[0] = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '0') {
if (s.charAt(i - 1) == '0' || s.charAt(i - 1) >= '3') {
return 0;
} else {
dp[i] = i - 2 >= 0 ? dp[i - 2] : 1;
}
} else if (s.charAt(i) >= '1' && s.charAt(i) <= '6') {
if (s.charAt(i - 1) == '0') {
dp[i] = dp[i - 1];
} else if (s.charAt(i - 1) >= '1' && s.charAt(i - 1) <= '2') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 1) + dp[i - 1];
} else {
dp[i] = dp[i - 1];
}
} else if (s.charAt(i) >= '7') {
if (s.charAt(i - 1) == '1') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 1) + dp[i - 1];
} else {
dp[i] = dp[i - 1];
}
}
}
return dp[s.length() - 1];
}
}
96. 不同的二叉搜索树
dp[i]代表以1,2,3 ... i 为结点组成的二叉搜索树的个数。
边界：
dp[0] = 1, dp[1] = 1
转移方程：
dp[i]代表以1,2,3 ... i 为结点组成的二叉搜索树的个数，遍历每个结点，让其作为根结点，假设根结点为j，那么它的左子树的结点个数为j-1，右子树的结点个数为i-j，以j为根结点组成的二叉树个数为dp[j-1] * dp[i-j]。 dp[i]的大小等于所有结点作为根结点的个数之和。
时间复杂度On2,空间复杂度On
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
97. 交错字符串
转化为是否存在一条路径可以从左上角，到达右下角。且每次只能向右走或者向下走。
dp[i][j]代表s1前i个字符与s2前j个字符能否交错形成s3的前i+j个字符。
边界：
第一行和第一列遇到第一个不匹配的字符之前，都是true。
转移方程：
在某i行j列中，只要上方一个格子是true，且s1的第i个字符与s3匹配，那么dp[i][j] = true。
或者只要左方一个格子是true，且s2的第j个字符与s3匹配，那么dp[i][j]也等于true。
时间复杂度On2，空间复杂度On2。
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
int len1 = s1.length(), len2 = s2.length();
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
for (int i = 1; i <= len1; i++) {
if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
dp[i][0] = true;
} else {
break;
}
}
for (int j = 1; j <= len2; j++) {
if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
dp[0][j] = true;
} else {
break;
}
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (dp[i - 1][j] == true && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = true;
} else if (dp[i][j - 1] == true && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = true;
}
}
}
return dp[len1][len2];
}
}
115. 不同的子序列
dp[i][j]代表s的前i个字符与t的前j个字符的不同子序列数。
边界：
如果t为空字符串，那么一定是s的子序列，dp[i][0] = 1。
转移方程：
1.如果i < j ，那么不可能存在t是s的子序列，dp[i][j] = 0
2.如果s的第i个字符等于t的第j个字符，即s.charAt(i - 1) == t.charAt(j - 1)。
那么可以分为两种情况，一种是s的第i个字符作为子序列，现在只需要计算s的前i-1个字符与t的前j-1个字符的不同子序列数即可。
另一种是s的第i个字符不作为子序列，只需要计算s的前i-1个字符与t的前j个字符的不同子序列数。
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
3.如果s的第i个字符不等于t的第j个字符，那么s的第i个字符一定不可能存在于子序列中，只需要计算s的前i-1个字符与t的前j个字符的不同子序列数。dp[i][j] = dp[i - 1][j]
class Solution {
public int numDistinct(String s, String t) {
int len1 = s.length(), len2 = t.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (i < j) {
continue;
}
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[len1][len2];
}
}
120. 三角形最小路径和
这道题从底往上推会容易很多。
dp[i][j] 代表从最下面一行出发，到达第i行第j个位置的最小路径和。
边界：
最后一行的最小路径和为它本身。
转移方程：
dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
时间复杂度On2，空间复杂度On2
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();
int[][] dp = new int[len][len];
for (int j = 0; j < len; j++) {
dp[len - 1][j] = triangle.get(len - 1).get(j);
}
for (int i = len - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
}
}
return dp[0][0];
}
}
优化：
由于dp[i][j]只与它的上一个状态有关，可以降到一维。
dp[i]代表之前求的那一层的第i列的最小路径和。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();
int[] dp = new int[len];
for (int i = 0; i < len; i++) {
dp[i] = triangle.get(len - 1).get(i);
}
for (int i = len - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
股票系列问题总结
可买入次数为1次或无限次时，dp数组二维；其余情况dp数组三维。
121. 买卖股票的最佳时机
方法一：
用一个变量minPrice记录历史价格最低点，每次在历史价格最低点买入，一次遍历之后就可以求出最大利润。
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int res = 0;
for (int i = 0; i < prices.length; i++) {
minPrice = Math.min(minPrice, prices[i]);
res = Math.max(prices[i] - minPrice, res);
}
return res;
}
}
方法二：
dp[i][j]代表第i天结束的时候，持有j份股票所获得的最大收益。
边界:
dp[0][0] = 0, dp[0][1] = -prices[i]
转移方程：
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], 0 - prices[i]);
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], 0 - prices[i]);//只能一次交易，所以dp[i-1][0] = 0
}
return dp[len - 1][0];
}
}
122. 买卖股票的最佳时机 II
方法一：
采用贪心的思想，只要每次第二天比当天价格高，那么就当天买第二天卖。
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
res += prices[i] - prices[i - 1];
}
}
return res;
}
}
方法二：
dp[i][j]代表第i天结束的时候，持有j份股票所获得的最大收益。
边界:
dp[0][0] = 0, dp[0][1] = -prices[i]
转移方程：
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i-1][0] - prices[i]);
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[len - 1][0];
}
}
123. 买卖股票的最佳时机 III
dp[i][j][k]代表第i天结束时，进行了j次买入交易，手中持有k份股票所获得的最大收益。
边界：
第0天结束时，无论买了多少次，最后手中还持有一份股票，收益为-prices[0]
dp[0][j][1] = -prices[0];
转移方程：
1.第i天，买了j次的情况下，手中持有0份股票：
第i天休息，那么dp[i][j][0] = dp[i-1][j][0]；
第i天卖出，那么dp[i][j][0] = dp[i - 1][j][1] + prices[i])
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
2.第i天，买了j次的情况下，手中持有1份股票：
第i天休息，那么dp[i][j][1] = dp[i-1][j][1]；
第i天买入，那么dp[i][j][1] = dp[i - 1][j - 1][0] - prices[i] ;
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int len = prices.length;
int[][][] dp = new int[len][3][2];
for (int j = 1; j <= 2; j++) {
dp[0][j][1] = -prices[0];
}
for (int i = 1; i < len; i++) {
for (int j = 2; j > 0; j--) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[len - 1][2][0];
}
}
88. 买卖股票的最佳时机 IV
此题和上一题几乎一样，只是可以买入交易的次数从2变为了任意值。
dp[i][j][k]代表第i天结束时，进行了j次买入交易，手中持有k份股票所获得的最大收益。
边界：
第0天结束时，无论买了多少次，最后手中还持有一份股票，收益为-prices[0]
dp[0][j][1] = -prices[0];
转移方程：
1.第i天，买了j次的情况下，手中持有0份股票：
第i天休息，那么dp[i][j][0] = dp[i-1][j][0]；
第i天卖出，那么dp[i][j][0] = dp[i - 1][j][1] + prices[i])
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
2.第i天，买了j次的情况下，手中持有1份股票：
第i天休息，那么dp[i][j][1] = dp[i-1][j][1]；
第i天买入，那么dp[i][j][1] = dp[i - 1][j - 1][0] - prices[i] ;
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
class Solution {
public int maxProfit(int k, int[] prices) {
if (k > 100000) {//内存超限，先加这个
return 1648961;
}
if (prices.length == 0) {
return 0;
}
int len = prices.length;
int[][][] dp = new int[len][k + 1][2];
for (int j = 1; j <= k; j++) {
dp[0][j][1] = -prices[0];
}
for (int i = 1; i < len; i++) {
for (int j = k; j > 0; j--) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[len - 1][k][0];
}
}
网友评论