动态规划的3个例子 最长序列 背包问题

1 最大子序和

题目: 给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路：

1. 定义一个一维数组dp，其中dp[i]表示以第i个元素为结尾的最大子序和。
2. 状态转移方程为dp[i] = max(dp[i-1]+nums[i], nums[i])，即用上一个位置的最大子序和和当前元素nums[i]相加，或者只选当前元素都可以得到一个以当前位置结尾的最大子序和。

Java代码实现：

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
        max = Math.max(max, dp[i]);
    }
    return max;
}

2 最长上升子序列

题目: 在一个未排序的整数数组中，找到最长的上升子序列的长度。

思路：

1. 注意审题, 这是最长的上升子序列, 不需要连续
2. 定义一个一维数组dp，其中dp[i]表示以第i个元素为结尾的最长上升子序列的长度
3. 所有元素初始状态为1，因为每个元素本身也构成一个长度为1的上升子序列。
4. 然后遍历数组，对于当前元素nums[i]，如果存在一个位置j在0 ~ i-1 之间，且nums[j]小于nums[i]，那么将 dp[i] 更新为 dp[j]+1
5. 用一个变量记录全局最大的dp值。

Java代码实现：

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

此处, 可以引出问题的变种: 在一个未排序的整数数组中，找到最长的连续上升子序列的长度。

思路：

1. 注意审题, 与上面区别, 此处是求这是最长连续的上升子序列
2. 定义一个一维数组dp，其中dp[i]表示以第i个元素为结尾的最长连续上升子序列的长度
3. 所有元素初始状态为1，因为每个元素本身也构成一个长度为1的上升子序列。
4. 然后遍历数组，如果nums[i] > nums[i-1], 那么将 dp[i] 更新为 dp[i-1]+1
5. 另外用一个变量记录全局最大的dp值。

依旧是Java代码实现：

public int longestRiseSerial(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

3 背包问题

题目: 有一个背包，容量为C，有n个物品，每个物品的重量为w[i]，价值为v[i]。如何在保证装入背包的物品总重量不超过C的情况下，使得装入的物品总价值最大？

思路：

1. 定义一个二维数组dp[i][j]，其中dp[i][j]表示前i个物品中，背包容量为j时的最大价值。
2. 若当前考虑的物品i的重量w[i]大于当前背包容量j，则dp[i][j] = dp[i-1][j]（不将此物品装入背包），
3. 否则dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（将此物品装入背包，可以用上一级商品的价值加上当前商品的价值）

Java代码实现：

public int knapsack(int[] w, int[] v, int C, int n) {
    int[][] dp = new int[n+1][C+1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            if (w[i-1] > j) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    return dp[n][C];
}

动态规划总结小笔记:

1. 对于动态规划的一维数组, 通常由一个变量组成问题, dp[i]表示结果, 其中i表示包括前i个变量

2. 对于动态规划的二维数组, 通常由两个变量组成问题, dp[i][j]表示结果, 其中i表示包括前i个变量一, 而j表示变量二为j时