区间DP

让字符串成为回文串的最少插入次数

leetcode 1312

思路： 跟求最长回文子序列一样。dp[i][j] 表示 让s[i:j] 变成回文串的最少插入数。 如果 s[i] == s[j]，则 dp[i][j] = dp[i + 1][j - 1] 否则 dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1。 边界值dp[i][i] = 0 以及 dp[i][i + 1] = 1 if s[i] != s[i + 1] else 0 。最后还可以空间压缩，一个格子依赖它的左下，下面，左边3个格子。顺序为从下到上，从左到右。用leftDown记录左下的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int minInsertions(String s1) {
        char[] s = s1.toCharArray();
        int n = s1.length();
        if(n==1){
            return 0;
        }
        int[] dp = new int[n];
        dp[n-1] = s[n-2] == s[n-1] ? 0 : 1;
        for(int i = n-3;i>=0;i--){
            int leftDown = dp[i+1],backUp;
            // dp[i] = 0
            dp[i+1] = s[i] == s[i+1] ? 0 :1;
            for(int j = i+2;j<n;j++){
                backUp = dp[j];
                if(s[i] == s[j]){
                    dp[j] = leftDown;
                }else {
                    dp[j] = Math.min(dp[j],dp[j-1]) + 1;
                }
                leftDown = backUp;
            }
        }
        return dp[n-1];
    }

预测赢家

leetcode 486

思路：dp[i][j]表示玩家1在i到j的区间内，能赢的最多分数。如果玩家1拿了i位置的数，那么玩家2只能拿i+1或者j位置的数，而玩家二应该选择能让玩家1拿更少的拿法。所以 p1 = nums[i] + Math.min(dp[i+2][j],dp[i+1][j-1]); 同理如果玩家1拿了j位置的数，那么玩家2只能拿i位置的数或者j-1位置的数，而玩家二应该选择能让玩家1拿更少的拿法。所以 p2 = nums[j] + Math.min(dp[i][j-2],dp[i+1][j-1]); 。 最后状态转移方程为 dp[i][j] = Math.max(p1,p2)； 初始化只有一个数的情况 dp[i][i] = nums[i]; 只有两个数的情况就拿最大的 dp[i][i+1] = Math.max(nums[i],nums[i+1]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean predictTheWinner(int[] nums) {
    int n = nums.length;
    if( (n&1) ==0 ){
        return true;
    }
    int[][] dp = new int[n][n];
    int sum = 0;
    for(int i=0;i<n;i++){
        dp[i][i] = nums[i];
        sum +=nums[i];
    }
    for(int i=0;i<n-1;i++){
        dp[i][i+1] = Math.max(nums[i],nums[i+1]);
    }
    for(int i = n - 3;i>=0;i--){
        for(int j = i+2;j<n;j++){
            int p1 = nums[i] + Math.min(dp[i+2][j],dp[i+1][j-1]);
            int p2 = nums[j] + Math.min(dp[i+1][j-1],dp[i][j-2]);
            dp[i][j] = Math.max(p1,p2);
        }
    }
    return dp[0][n-1] >= (sum - dp[0][n-1]);
}

多边三角形剖分的最低得分

leetcode 1039

思路： dp[i][j] 表示 i到j的区间内，多边形能得到的最低得分。 dp[i][j] = Math.min(dp[i][k] + dp[k][j] + s[i]s[j]s[k]); k为i到j的区间内任意一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int minScoreTriangulation(int[] values) {
    int n = values.length;
    int[][] dp = new int[n][n];
    for(int i = n-3;i>=0;i--){
        for(int j = i+2;j<n;j++){
            dp[i][j] = Integer.MAX_VALUE;
            for(int m = i+1;m<j;m++){
                dp[i][j] = Math.min(dp[i][m]+dp[m][j]+ values[i]*values[j]*values[m],dp[i][j]);
            }
        }
    }
    return dp[0][n-1];
}

树形DP

套路：

套路
套路

最大BST子树

leetcode 333

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
28
29
30
31
32
33
34
35
36
37
38
public static int largestBSTSubtree(TreeNode root) {
	return f(root).maxBstSize;
}

public static class Info {
	public long max;
	public long min;
	public boolean isBst;
	public int maxBstSize;

	public Info(long a, long b, boolean c, int d) {
		max = a;
		min = b;
		isBst = c;
		maxBstSize = d;
	}
}

public static Info f(TreeNode x) {
	if (x == null) {
		return new Info(Long.MIN_VALUE, Long.MAX_VALUE, true, 0);
	}
	Info infol = f(x.left);
	Info infor = f(x.right);
	// 左 4信息
	// 右 4信息
	// x 整合出4信息返回
	long max = Math.max(x.val, Math.max(infol.max, infor.max));
	long min = Math.min(x.val, Math.min(infol.min, infor.min));
	boolean isBst = infol.isBst && infor.isBst && infol.max < x.val && x.val < infor.min;
	int maxBSTSize;
	if (isBst) {
		maxBSTSize = infol.maxBstSize + infor.maxBstSize + 1;
	} else {
		maxBSTSize = Math.max(infol.maxBstSize, infor.maxBstSize);
	}
	return new Info(max, min, isBst, maxBSTSize);
}

最大BST子树和

leetcode 1317

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 提交如下的方法
	public static int maxSumBST(TreeNode root) {
		return f(root).maxBstSum;
	}

	public static class Info {
		// 为什么这里的max和min是int类型？
		// 因为题目的数据量规定，
		// 节点值在[-4 * 10^4，4 * 10^4]范围
		// 所以int类型的最小值和最大值就够用了
		// 不需要用long类型
		public int max;
		public int min;
		public int sum;
		public boolean isBst;
		public int maxBstSum;

		public Info(int a, int b, int c, boolean d, int e) {
			max = a;
			min = b;
			sum = c;
			isBst = d;
			maxBstSum = e;
		}
	}

	public static Info f(TreeNode x) {
		if (x == null) {
			return new Info(Integer.MIN_VALUE, Integer.MAX_VALUE, 0, true, 0);
		}
		Info infol = f(x.left);
		Info infor = f(x.right);
		int max = Math.max(x.val, Math.max(infol.max, infor.max));
		int min = Math.min(x.val, Math.min(infol.min, infor.min));
		int sum = infol.sum + infor.sum + x.val;
		boolean isBst = infol.isBst && infor.isBst && infol.max < x.val && x.val < infor.min;
		int maxBstSum = Math.max(infol.maxBstSum, infor.maxBstSum);
		if (isBst) {
			maxBstSum = Math.max(maxBstSum, sum);
		}
		return new Info(max, min, sum, isBst, maxBstSum);
	}

在二叉树中分配硬币

leetcode 979

思路：每棵树需要的信息是总节点数，总硬币数，移动次数。 那么对于父节点只需要把左树多的硬币移动到右树去，加上左右的次数返回即可。

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
28
29
public class Info{
    int nodeSum;
    int moSum;
    int cnt;
    public Info(int nodeSum,int moSum,int cnt){
        this.nodeSum = nodeSum;
        this.moSum = moSum;
        this.cnt = cnt;
    }
}

public int distributeCoins(TreeNode root) {
    return findDBC(root).cnt;
}

public Info findDBC(TreeNode root){
    if(root == null){
        return new Info(0,0,0);
    }
    Info left = findDBC(root.left);
    Info right = findDBC(root.right);

    int nodeSum = left.nodeSum + right.nodeSum + 1;
    int moSum = left.moSum + right.moSum + root.val;

    int cnt = Math.abs(left.nodeSum - left.moSum) + Math.abs(right.nodeSum - right.moSum) + left.cnt + right.cnt;

    return new Info(nodeSum,moSum,cnt);
}

没有上司的舞会

思路：跟leetcode上的打家劫舍3一样。每个节点选择偷跟不偷。如果偷那么子节点只能不偷。不偷那么子节点可以偷也可以不偷求最大值即可。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.io.*;
import java.util.Arrays;

public class Main {

    public static int MAXN = 6001;
    public static int MAXM = 6000;

    public static int[] head = new int[MAXN];
    public static int[] next = new int[MAXM];
    public static int[] to = new int[MAXM];
    public static int[] boss = new int[MAXN];
    public static int[] weight = new int[MAXN];

    public static int cnt;

    public static void build(int n){
        Arrays.fill(head,0,n+1,0);
        Arrays.fill(boss,0,n+1,0);
        cnt = 1;
    }

    public static void add(int u,int v){
        next[cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt++;
        boss[v]++;
    }

    public static class Info{
        int no;
        int yes;
        public Info(int a,int b){
            no = a;
            yes = b;
        }
    }

    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int)in.nval;
            build(n);
            for(int i=1;i<=n;i++){
                in.nextToken(); weight[i] = (int)in.nval;
            }
            for(int i=1,u,v;i<n;i++){
                in.nextToken(); u = (int) in.nval;
                in.nextToken(); v = (int) in.nval;
                add(v,u);
            }
            int Boss = 1;
            //找到头节点
            for(int i = 1;i<=n;i++){
                if(boss[i] == 0){
                    Boss = i;
                    break;
                }
            }
            Info ans = compute(Boss);
            out.println(Math.max(ans.no,ans.yes));
        }
        out.flush();
        out.close();
        br.close();
    }

    public static Info compute(int node){
        //没有出边
        if(head[node] == 0){
            return new Info(0,weight[node]);
        }

        int no = 0;
        int yes = weight[node];

        for(int ie = head[node];ie>0;ie = next[ie]){
            Info p = compute(to[ie]);
            no+=Math.max(p.yes,p.no);
            yes+=p.no;
        }

        return new Info(no,yes);
    }

}

监控二叉树

leetcode 968

思路：其实这道题代码并不难，难的是思路。我们给每个节点赋予三种状态： 0，1，2。 0表示当前节点没有被监控，1表示当前节点被监控，但是没有摄像头，2表示当前节点被监控且安装了摄像头。

  1. 如果一个节点的左右两个节点有一个状态为0，那么这个节点必须安装摄像头，返回2状态，不然他的孩子就永远无法被监控。
  2. 如果两个孩子有一个有摄像头，那自己就返回1状态，因为自己被监控了
  3. 如果两个孩子都被监控了但是没有摄像头（都是1状态）。那么自己就以0状态返回。那这时候为什么不给自己装个摄像头呢？因为自己就只会让父节点跟自己两个节点被新监控到，但是如果把装摄像头的机会让给父节点，那么这个摄像头就有可能覆盖更多的节点。

综上一个节点的状态返回依赖两个孩子的状态，这就是典型的树形dp。 初始化空节点为1状态即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int ans;

public static int minCameraCover(TreeNode root) {
    ans = 0;
    return findMCC(root) == 0 ? ans+1:ans;
}
public static int findMCC(TreeNode node){
    if(node == null){
        return 1;
    }
    int left = findMCC(node.left);
    int right = findMCC(node.right);
    if(left == 0 || right == 0){
        ans++;
        return 2;
    }
    if(left == 2 || right == 2){
        return 1;
    }
    return 0;
}

状压DP

状态dp就是在带记忆化搜索的时候，把路径信息用二进制表示。一般路径信息不会很大，小于20个可以考虑状态dp。有点像用位运算的n皇后。

我能赢吗

leetcode 464

思路：用一个status表示当前拿数的状态。 比如 0011011 表示第1，2，4，5的数字还没拿其他已经拿了。然后dfs(int status,int res ,int[] dp) 表示在当前状态下，还剩余res的和的情况下，先手能不能赢。那么只用枚举剩下的数字，如果拿了这个数字之后让对方先手不能赢，那么自己就可以赢。然后dp[]表示，在当前这个状态下，先手能不能赢。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal == 0) {
            // 来自题目规定
            return true;
        }
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) {
            // 如果1~n数字全加起来
            // 累加和和是n * (n+1) / 2，都小于m
            // 那么不会有赢家，也就意味着先手不会获胜
            return false;
        }
        int status = (1<<maxChoosableInteger) - 1;
        int[] dp = new int[1<<(maxChoosableInteger)];
        return findCIW(status,desiredTotal,dp);
    }

    public boolean findCIW(int status,int res,int[] dp){
        if(res <= 0){
            return false;
        }
        if(dp[status] != 0){
            return dp[status] == 1;
        }

        int temp = status;
        boolean ans = false;
        while(temp!=0){
            int pos = temp & (-temp);
            int n = 0,m=pos;
            while(m!=0){
                m>>=1;
                n++;
            }
            temp ^= pos;
            if(!findCIW(status ^ pos,res - n,dp)){
                ans = true;
                break;
            }
        }
        dp[status] = ans ? 1 : -1;
        return ans;
    }

火柴拼接正方形

Leetcode 473

思路: 就是按dfs的思路。staus表示当前剩余的火柴，len表示当前拼接的边长,res表示还需要几条边。依次枚举每个剩下的火柴，如果火柴加上当前边长，那么下次递归就len = 0,res = res-1。如果小于那下次递归就 len = len + 火柴长度 ，res = res。 如果大于那就不会要这个火柴。当火柴用完的时候看边品完没有即可。dp[]表示在当前状态下能不能拼出剩余的正方形。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public boolean makesquare(int[] m) {
        int sum = 0;
        int n = m.length;
        for (int i : m) {
            sum+=i;
        }
        if(sum % 4!=0){
            return false;
        }
        int status = (1<<n) - 1;
        int[] dp = new int[1<<n];
        return findMQ(m,status,0,sum/4,4,dp);
    }

    public boolean findMQ(int[] m,int status,int len,int limit,int res,int[] dp){
        if(status == 0){
            return res == 0;
        }
        if(dp[status] != 0){
            return dp[status] == 1;
        }
        //依次枚举还能拿的火柴
        int temp = status;
        boolean ans = false;
        while(temp!=0){
            int pos = temp & (-temp);
            int n=-1,k=pos;
            while(k!=0){
                k>>=1;
                n++;
            }
            //n就是能拿的火柴
            int slen = m[n];
            temp ^= pos;
            if(slen + len == limit){
                ans = findMQ(m,status ^ pos,0,limit,res-1,dp);
            }else if(slen + len < limit){
                ans = findMQ(m,status^pos,slen+len,limit,res,dp);
            }else {
                continue;
            }
            if(ans){
                break;
            }
        }
        dp[status] = ans ? 1 : -1;
        return ans;
    }