区间dp
# 回文串问题
# 516. 最长回文子序列 (opens new window)
# 5. 最长回文子串 (opens new window)
# 1312. 让字符串成为回文串的最少插入次数 (opens new window)
# 647. 回文子串 (opens new window)
# 1039. 多边形三角剖分的最低得分 (opens new window)
# 877. 石子游戏 (opens new window)
方法一：记忆化搜索
class Solution {
int[][] memo;
public boolean stoneGame(int[] piles) {
int n = piles.length;
this.memo = new int[n][n];// 区间内重复计算
for(int[] row:memo){
Arrays.fill(row,Integer.MIN_VALUE);
}
return dfs(piles,0,n-1)>0;
}
// 计算先手可以获得的分数
int dfs(int[] piles,int l,int r){
// 区间是偶数，最后一个必须被取走
if(l==r){
return piles[l];
}
if(memo[l][r]!=Integer.MIN_VALUE){
return memo[l][r];
}
// 返回的是相对分数
return memo[l][r] = Math.max(piles[l]-dfs(piles,l+1,r),
piles[r]-dfs(piles,l,r-1));
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
方法二：动态规划
class Solution {
public boolean stoneGame(int[] piles) {
int n = piles.length;
// 区间内先手获得的相对分数
int[][] dp = new int[n][n];
// 最后一堆石头必须被选
for(int i=0;i<n;i++){
dp[i][i] = piles[i];
}
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
dp[i][j] = Math.max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1]);
}
}
return dp[0][n-1]>0;
}
}
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
# 486. 预测赢家 (opens new window)
方法一：记忆化搜索
class Solution {
int[][] memo;
public boolean predictTheWinner(int[] nums) {
int n = nums.length;
this.memo = new int[n][n];
for(int[] row:memo){
Arrays.fill(row,Integer.MIN_VALUE);
}
return dfs(nums,0,n-1)>=0;
}
int dfs(int[] nums,int l,int r){
// if(l>r){
// return 0;
// }
if(l==r){
return nums[l];
}
if(memo[l][r]!=Integer.MIN_VALUE){
return memo[l][r];
}
return memo[l][r] = Math.max(nums[l]-dfs(nums,l+1,r),
nums[r]-dfs(nums,l,r-1));
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
方法二：动态规划
class Solution {
public boolean predictTheWinner(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];
for(int i=0;i<n;i++){
dp[i][i] = nums[i];
}
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
dp[i][j] = Math.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
}
}
return dp[0][n-1]>=0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 312. 戳气球 (opens new window)
方法一：记忆化搜索
class Solution {
int[][] memo;
int[] a;
public int maxCoins(int[] nums) {
int n = nums.length;
this.memo = new int[n+2][n+2];
this.a = new int[n+2];
a[0]=1;a[n+1]=1;
for(int i=0;i<n;i++){
a[i+1] = nums[i];
}
for(int[] row:memo){
Arrays.fill(row,-1);
}
return dfs(0,n+1);
}
int dfs(int l,int r){
if(memo[l][r]!=-1){
return memo[l][r];
}
int ans = 0;
for(int i=l+1;i<r;i++){
ans = Math.max(ans,dfs(l,i)+a[l]*a[i]*a[r]+dfs(i,r));
}
return memo[l][r] = ans;
}
}
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
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
方法二：动态规划
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] a = new int[n+2];
a[0] = a[n+1] = 1;
for(int i=0;i<n;i++){
a[i+1] = nums[i];
}
int[][] dp = new int[n+2][n+2];
for(int i=n;i>=0;i--){
for(int j=i+1;j<n+2;j++){
for(int k=i+1;k<j;k++){
dp[i][j] = Math.max(dp[i][j],
dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
}
}
}
return dp[0][n+1];
}
}
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
# 375. 猜数字大小 II (opens new window)
方法一：记忆化搜索
class Solution {
int[][] memo;
public int getMoneyAmount(int n) {
this.memo = new int[n+2][n+2];
return dfs(1,n);
}
int dfs(int l,int r){
if(l>=r) return 0;
if(memo[l][r]!=0){
return memo[l][r];
}
int ans = Integer.MAX_VALUE;
for(int k=l;k<=r;k++){
//备用现金未左右两边最小代价的最大值+本身
ans = Math.min(ans,Math.max(dfs(l,k-1),dfs(k+1,r))+k);
}
return memo[l][r] = ans;
}
}
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
方法二：动态规划
class Solution {
public int getMoneyAmount(int n) {
//区间内获胜最少钱数
int[][] dp = new int[n+2][n+2];
for(int i=n-1;i>=1;i--){
for(int j=i+1;j<=n;j++){
int min = Integer.MAX_VALUE;
for(int k=i;k<=j;k++){
min = Math.min(min,Math.max(dp[i][k-1],dp[k+1][j])+k);
}
dp[i][j] = min;
}
}
return dp[1][n];
}
}
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