算法9-动态规划

动态规划基础知识

解题步骤

• 1 确定状态
  解动态规划需要开一个数组，数组的每个元素f[i] 或者 f[i][j] 表示什么；
  步骤：研究最优策略的最后一步；化为子问题；
• 2 转移方程
  根据子问题定义直接得到
• 3 初始条件、边界情况
  初始条件：f[0] f[1]
  边界条件：数组的边界、越不越界问题
• 4 计算顺序
  利用之前的计算结果

案例

分割等和子集（leecode416 背包问题）（NP完全问题）

描述
给你一个 只包含正整数 的 非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

案例
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。

分析
①自己
将数组分成两个数组，比较两个数组的和是否一样。这种思路；
②参考1
提取数组元素子集，看子集之和是否是整个数组元素之和的一半。

动态规划1

class Solution {
    public boolean canPartition(int[] nums) {
		// 分析
		int n = nums.length;
		// 求数组元素之和 与 最大值
		int sums = 0,maxNum = 0;
		for(int num : nums){
			sums += num;
			maxNum = Math.max(num,maxNum);
		}
		// 如果数组长度小于2 返回false，因为无法分成两个集合
		if(n < 2)
			return false;
		// 如果sums结果为奇数，没有办法分成两个数组 且两者元素之和相等
		if(sums %2 != 0)
			return false;
		
		// 目标值target
		int target = sums / 2;
		// 如果元素的最大值 大于 目标值 说明数组无法分成两个元素值之和相等的 情况
		if(maxNum > target)
			return false;

		// 确定状态 dp[i][j] 表示 从数组下标0-i中选取若干个元素，是否可以等于j
		boolean[][] dp = new boolean[n][target+1];
		
		// 特殊值
		// 不选值的时候，且目标值是0 则结果全是true
		for(int i = 0 ; i < n; i++){
			dp[i][0] = true;
		}
		// 只有一个值的时候，j等于它自己本身 则结果为true
		dp[0][nums[0]] = true;

		// 转移方程
		for(int i = 1 ; i < n ; i++){
			int num = nums[i];
			for(int j = 1 ; j <= target; j++){
				if(j > num){
					dp[i][j] = dp[i-1][j-num] | dp[i-1][j];
				}else{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		return dp[n-1][target];
    }
}
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

动态规划2

因为本行的dp只和上一行的dp有关系，所以可以将状态从二维转为一维。

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sums = 0 , maxNum = 0;
        for(int num : nums){
            sums += num;
            if(num > maxNum) maxNum = num;
        }
        int target = sums / 2 ;
        if(n < 2 || sums %2 != 0 || maxNum > target)
            return false;

        boolean[] dp = new boolean[target+1];
        // 不选元素 
        dp[0] = true;
        // 只有一个元素，
        dp[nums[0]] = true;
        for(int i = 1 ; i < n ; i++){
            for(int j = target ; j > 0 ; --j){
                if(j >= nums[i])
                    dp[j] = dp[j] | dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}
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