线性dp
# 198. 打家劫舍 (opens new window)
方法一：记忆化搜索
class Solution {
int[] memo;
int[] nums;
public int rob(int[] nums) {
int n = nums.length;
this.nums = nums;
this.memo = new int[n];
Arrays.fill(memo,-1);
return dfs(0);
}
int dfs(int i){
if(i>=nums.length){
return 0;
}
if(memo[i]!=-1){
return memo[i];
}
return memo[i] = Math.max(dfs(i+1),dfs(i+2)+nums[i]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
方法二：动态规划
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n+2];
for(int i=0;i<n;i++){
dp[i+2] = Math.max(dp[i+1],dp[i]+nums[i]);
}
return dp[n+1];
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
优化；
class Solution { public int rob(int[] nums) { int d0=0,d1=0; for(int x:nums){ int tmp = Math.max(d1,d0+x); d0 = d1; d1 = tmp; } return d1; } }1
2
3
4
5
6
7
8
9
10
11
# 213. 打家劫舍 II (opens new window)
class Solution {
int[] nums;
public int rob(int[] nums) {
this.nums = nums;
int n = nums.length;
return Math.max(nums[0]+dfs(2,n-1),dfs(1,n));
}
int dfs(int l,int r){
int d0=0,d1=0;
for(int i=l;i<r;i++){
int tmp = Math.max(d0+nums[i],d1);
d0 = d1;
d1 = tmp;
}
return d1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 子数组问题
# 53. 最大子数组和 (opens new window)
方法一：记忆化搜索
class Solution {
int[] nums;
int[] memo;
public int maxSubArray(int[] nums) {
int n = nums.length;
this.nums = nums;
this.memo = new int[n];
int ret = nums[0];
for(int i=1;i<n;i++){
ret = Math.max(ret,dfs(i));
}
return ret;
}
int dfs(int i){
if(i<0) return 0;
if(memo[i]!=0) return memo[i];
return memo[i] = Math.max(dfs(i-1)+nums[i],nums[i]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
方法二：动态规划
状态定义：以
nums[i]结尾的连续子数组的最大和；
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for(int i=1;i<n;i++){
if(dp[i-1]>0)
dp[i] = dp[i-1]+nums[i];
else
dp[i] = nums[i];
}
int res = dp[0];
for(int i=1;i<n;i++){
res = Math.max(res,dp[i]);
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 152. 乘积最大子数组 (opens new window)
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
if(n==0)
return 0;
int[] maxDp = new int[n];
int[] minDp = new int[n];
maxDp[0] = nums[0];
minDp[0] = nums[0];
for(int i=1;i<n;i++){
if(nums[i]>=0){
maxDp[i] = Math.max(nums[i],maxDp[i-1]*nums[i]);
minDp[i] = Math.min(nums[i],minDp[i-1]*nums[i]);
}else{
maxDp[i] = Math.max(nums[i],minDp[i-1]*nums[i]);
minDp[i] = Math.min(nums[i],maxDp[i-1]*nums[i]);
}
}
int ret = maxDp[0];
for(int i=1;i<n;i++){
ret = Math.max(ret,maxDp[i]);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 2321. 拼接数组的最大分数 (opens new window)
# 2771. 构造最长非递减子数组 (opens new window)
# 1186. 删除一次得到子数组最大和 (opens new window)
# 118. 杨辉三角 (opens new window)
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
for(int i=0;i<numRows;i++){
List<Integer> row = new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0 || j==i){
row.add(1);
}else{
row.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
}
}
ret.add(row);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 45. 跳跃游戏 II (opens new window)
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp,Integer.MAX_VALUE/2);
dp[0] = 0;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(i-j<=nums[j]){
dp[i] = Math.min(dp[j]+1,dp[i]);
}
}
}
return dp[n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 55. 跳跃游戏 (opens new window)
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[0] = true;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(dp[j] && (i-j)<=nums[j]){
dp[i] = true;
break;
}
}
}
return dp[n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
不同定义：
class Solution { public boolean canJump(int[] nums) { int n = nums.length; if(n==1) return true; if(nums[0]==0) return false; // i点之前能跳的最远距离 int[] dp = new int[n]; dp[0] = nums[0]; for(int i=1;i<n-1;i++){ dp[i] = Math.max(dp[i-1],nums[i]+i); if(dp[i]>=n-1) return true; if(dp[i]==i) return false; } return true; } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 91. 解码方法 (opens new window)
# 650. 只有两个键的键盘 (opens new window)
# 552. 学生出勤记录 II (opens new window)
# 403. 青蛙过河 (opens new window)
# 343. 整数拆分 (opens new window)
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n+1];//长度为i的绳子减为m段最大乘积
dp[1] = 1;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
// 前j段剪或不剪
dp[i] = Math.max(dp[i],Math.max(dp[j]*(i-j),j*(i-j)));
}
}
return dp[n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 1262. 可被三整除的最大和 (opens new window)
记忆化搜索：
class Solution {
int[][] memo;
int[] nums;
public int maxSumDivThree(int[] nums) {
int n = nums.length;
this.nums = nums;
this.memo = new int[n][3];
for(int[] row:memo){
Arrays.fill(row,-1);
}
return dfs(n-1,0);
}
int dfs(int i,int j){
if(i<0){
return j==0?0:Integer.MIN_VALUE;
}
if(memo[i][j]!=-1){
return memo[i][j];
}
return memo[i][j] = Math.max(dfs(i-1,j),dfs(i-1,(j+nums[i])%3)+nums[i]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22