动态规划专题

发表于 | 分类于 ，

动态规划概述：

　　动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。它利用各阶段之间的关系，逐个求解，最终求得全局最优解。在设计动态规划算法时，需要确认原问题与子问题、动态规划状态、边界状态值、状态转移方程等关键要素。
　　动态规划与分治算法类似，基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但动态规划与分治
算法不同的是，适用于动态规划求解的问题，经分解得到的子问题往往不是互相独立的。（即下一阶段的求解是建立在上一个子阶段的解的基础之上的。）

动态规划题目常见类型：

按问题特性分：
　　1.计数型
　　　　有多少种方式/方法...？
　　2.求最值
　　3.求存在性
　　　　是否能？能不能？（true or false）
按求解过程（状态方程）分：
　　1.数组型
　　2.背包型
　　3.字符串型

求解思路与步骤：

　　1.分析题目是否是动态规划题目
　　2.确定原问题与子问题
　　3.确定状态
　　4.确定边界状态的值
　　5.找出状态转移方程
　　6.code
　　注意：在解题过程可以先枚举找出状态转移关系，同时注意应用“选与不选”的思路

例题分析：

数组类型DP

　　1.爬楼梯（LeetCode70）
　　　　分析：计数型问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求n阶台阶的走法，子问题为求1阶台阶、2阶台阶、…、n-1阶台阶的走法
　　　　确定状态：此题状态单一，第i个状态即为i阶台阶的所有走法数量。
　　　　边界状态：i=1时，dp[i]=1，i=2时，dp[i]=2；
　　　　状态转移方程：dp[i] = dp[i-1]+dp[i-2];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int climbStairs1(int n) {
	int[] dp = new int[n];
	if (n == 1) {
		return 1;
	}
	if (n == 2) {
		return 2;
	}
	dp[0] = 1;
	dp[1] = 2;
	for(int i = 2;i < n;i++) {
		dp[i] = dp[i-1]+dp[i-2];
	}
	return dp[n-1];
}

　　2.打家劫舍
　　　　你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求到第n个房屋的最大收益，子问题为求第1个房屋的最大收益、第2个房屋的最大收益、…、第n-1个房屋的最大收益
　　　　确定状态：此题状态单一，第i个状态即为第i个房屋的最大收益.
　　　　边界状态：i=1时，dp[i]=nums[0]，i=2时，dp[i]=Math.max(nums[0], nums[1])；
　　　　状态转移方程：dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])(包含第i个房屋偷或者不偷两种选择);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  public int rob(int[] nums) {
      if (nums == null || nums.length < 1) {
	return 0;
}
      if (nums.length == 1) {
	return nums[0];
}
      if (nums.length == 2) {
	return Math.max(nums[0], nums[1]);
}
      int[] dp = new int[nums.length];
      dp[0] = nums[0];
      dp[1] = Math.max(nums[0], nums[1]);
      for(int i = 2;i < dp.length;i++) {
      	dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
      }
      return dp[dp.length-1];
  }

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

　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求以第n个数字结尾的最大字段和，子问题为求以第1、2、…、n-1个数字结尾的最大字段和。注意dp[n]并不是前n个数字组成的数组的最大字段和，即不是最终答案
　　　　确定状态：第i个状态即为以第i个数字结尾的最大字段和
　　　　边界状态：i=1时，dp[i]=nums[0]
　　　　状态转移方程：dp[i] = nums[i](dp[i-1] <= 0) or num[i]+dpi-1(包含第i个房屋偷或者不偷两种选择);

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray1(int[] nums) {
	int ans = nums[0];
	int sum = 0;
	for(int num:nums) {
		if (sum > 0) {
			sum += num;
		}else {
			sum = num;
		}
		ans = Math.max(ans, sum);
	}
	return ans;
}

　　4.零钱兑换（LeetCode322）
　　　　给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能
组成总金额，返回 -1。

　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为总金额为n时，最少需要的硬币个数，子问题为总金额为1、2、…n-1时，最少需要的硬币个数
　　　　确定状态：第i个状态即为总金额为i时最少所需的硬币个数。
　　　　边界状态：i=0时，dp[i]=0
　　　　状态转移方程：dp[i] = min(dp[i-ooins[j]])+1;
　　　　注意：此题不能从数组着手，从数组着手无法确定状态转移方程。同时注意考虑有的金额无法凑出的情况，此时需要返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int coinChange1(int[] coins, int amount) {
    int[] dp = new int[amount+1];
    for(int i = 0;i < amount+1;i++) {
    	dp[i] = -1;
    }
    dp[0] = 0;
    for(int i = 1;i < amount+1;i++) {
    	for(int j = 0;j < coins.length;j++) {
    		if (i - coins[j] >= 0 && dp[i-coins[j]] != -1) {
	if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1) {
		dp[i] = dp[i - coins[j]] + 1;
	}
}
    	}
    }
    return dp[amount];
}

　　扩展：零钱兑换问题在特定的零钱组合（任意面额是比自己小的面额的倍数关系）下是可以使用贪心算法进行解题，但同样在很多零钱组合下使用贪心算法解此类题是错误的。

　　5.三角形最小路径和（LeetCode120）
　　
　　6.最长上升子序列（LeetCode300，与LeetCode674对比）
　　　　给定一个无序的整数数组，找到其中最长上升子序列的长度。

　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求以第n个数为结尾的最长上升子序列的长度，子问题为求以第1、2、…、n-1个数为结尾的最长上升子序列的长度。
　　　　确定状态：第i个状态即为以第i个数为结尾的最长上升子序列的长度。
　　　　边界状态：i=0时，dp[i]=1
　　　　状态转移方程：dp[i] = max(dp[0]+1(num[i]>num[0]),dp[1]+1(num[i]>num[1])…dp[i-1]+1(num[i-1]>num[i-1]))
　　　　注意：此题与最大字段和类似，dp[i]并不表示最终的结果。很多动态规划题都是如此

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// dp
   public int lengthOfLIS(int[] nums) {
   	if (nums == null || nums.length < 1) {
		return 0;
	}
       int[] dp = new int[nums.length];
       for(int i = 0;i < dp.length;i++) {
       	dp[i] = 1;
       }
       int result = dp[0];
       for(int i = 1;i < dp.length;i++) {
       	for(int j = 0;j < i;j++) {
       		if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
       	}
       	if (result < dp[i]) {
			result = dp[i];
		}
       }
       return result;
   }

　　　　优化：尽管使用了动态规划，但此题的时间复杂度仍然有O(n2)，时间复杂度偏高。我们可以采用动态规划+二分查找的方式进行优化。
　　　　我们利用一个数组dp[i]存储到第i个数字的最长上升子序列，因此，循环过程中，每到来一个数字m，如果该数字大于数组末尾数字，则可直接添加在数组的末尾，否则的话，我们需要从头扫描dp，当遇到第一个大于等于m的数字时，我们需要利用m替换掉该数字。如此以来，虽然数组中所存储的不一定是最长上升子序列，但数组中所含元素的个数一定是最长上升子序列。而从头扫描dp个过程可用二分查找实现，因此时间复杂度可以降低到O(nlogn)。
　　　　其实这种思路的本质是把最终所求值用数组的长度来表示了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  // dp+二分查找
  public int lengthOfLIS1(int[] nums) {
  	if (nums == null || nums.length < 1) {
	return 0;
}
  	int[] dp = new int[nums.length];
  	int len = 0;
  	for(int num:nums) {
  		int i = Arrays.binarySearch(dp, 0, len, num);
  		if (i < 0) {
		i = -i-1;
	}
  		dp[i] = num;
  		if (i == len) {
		len++;
	}
  	}
  	return len;
  }

　　7.最小路径和
　　　　给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
　　　　说明：每次只能向下或者向右移动一步。

　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求以第n个数为结尾的最长上升子序列的长度，子问题为求以第1、2、…、n-1个数为结尾的最长上升子序列的长度。
　　　　确定状态：第i个状态即为以第i个数为结尾的最长上升子序列的长度。
　　　　边界状态：i=0时，dp[i]=1
　　　　状态转移方程：dp[i] = max(dp[0]+1(num[i]>num[0]),dp[1]+1(num[i]>num[1])…dp[i-1]+1(num[i-1]>num[i-1]))
　　　　注意：此题与最大字段和类似，dp[i]并不表示最终的结果。很多动态规划题都是如此

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// dp
   public int lengthOfLIS(int[] nums) {
   	if (nums == null || nums.length < 1) {
		return 0;
	}
       int[] dp = new int[nums.length];
       for(int i = 0;i < dp.length;i++) {
       	dp[i] = 1;
       }
       int result = dp[0];
       for(int i = 1;i < dp.length;i++) {
       	for(int j = 0;j < i;j++) {
       		if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
       	}
       	if (result < dp[i]) {
			result = dp[i];
		}
       }
       return result;
   }

　　8.地下城游戏（LeetCode174）

背包型DP

0-1背包

完全背包

参考链接

背包九讲