数据结构和算法-动态规划

怎样判断是否是动态规划问题

  1. 有多少种走法
  2. 求最大最小值
  3. 是否存在

线性DP

1. 单串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int lengthOfLIS(int[] nums) {
    int len = nums.length;
    if (len == 0) return 0;
    int res = 0;
    int[] dp = new int[len];
    for (int i=0; i<nums.length; i++) {
        // 从nums[0]...nums[i-1]中，找到小于nums[i]的项，并且从中选择最大的一个
        int max = 0;
        for (int j=0; j<i; j++) {
            if (nums[j] < nums[i]) {
                max = Math.max(max, dp[j]);
            }
        }
        dp[i] = max + 1;
        res = Math.max(res, dp[i]);
    }
    return res;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxSubArray(int[] nums) {
    if (nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int res = dp[0];
    for (int i=1; i<nums.length; i++) {
        int preSum = (dp[i-1] > 0 ? dp[i-1] : 0)
        // 连续子序 
        dp[i] = preSum + nums[i];
        // 不连续子序
        // dp[i] = preSum + (nums[i] > 0 ? nums[i] : 0);
        res = Math.max(res, dp[i]);
    }
    return res;

1
2
3
4
5
6
7
8
9
10
11
12
public int rob(int[] nums) {
    int N = nums.length;
    if (N == 0) return 0;
    int[][] dp = new int[N][2];
    dp[0][0] = 0;
    dp[0][1] = nums[0];
    for (int i=1; i<N; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = (i < 2 ? 0 : Math.max(dp[i-2][0], dp[i-2][1])) + nums[i];
    }
    return Math.max(dp[N-1][0], dp[N-1][1]);

区间DP

树型DP

背包dP