dp动态规划经典案例

dp动态规划算法总结

• 基本思想
• • 核心是将一个问题分解成为若干个子问题
  • 什么是动态规划
  • 适用问题
• 案例
• • 爬楼梯
  • 01背包

基本思想

是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

核心是将一个问题分解成为若干个子问题

什么是动态规划

1. 动态规划（Dynamic Programming）对于子问题重叠的情况特别有效，因为它将子问题的解保存在表格中，当需要某个子问题的解时，直接取值即可，从而避免重复计算！
2. 动态规划是一种灵活的方法，不存在一种万能的动态规划算法可以解决各类最优化问题（每种算法都有它的缺陷）。所以除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，用灵活的方法建立数学模型，用创造性的技巧去求解。

适用问题

1. 最优化原理：最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构
2. 无后项性：每个状态都是过去历史的一个完整总结（某状态以后的过程不会影响以前的状态）
3. 子问题重叠问题：我们必须保证我们分割成的子问题也能按照相同的方法分割成更小的自问题， 并这些自问题的最终分割情况是可以解决的。

案例

爬楼梯

• 题目：有一个楼梯总共n个台阶，只能往上走，每次只能上1个、2个台阶，总共有多少种走法。
  1. 比如，每次走1级台阶，一共走10步，这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。
  2. 再比如，每次走2级台阶，一共走5步，这是另一种走法。我们可以简写成 2,2,2,2,2。
• 分析：假如只差一步就能走完整个楼梯，要分为几种情况？因为每一步能走一级或者两级台阶，所以有如下两种情况： 假设n=10
  1. 最后一步走2级台阶，也就是从8级到10级
  2. 最后一步走1级台阶，也就是从9级到10级
• 公式：F(n) = F(n-1)+F(n-2) n>2 ; F(n) = n n<=2;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dp = new int[n+1];
		for (int i = 0; i <= n; i++) {
			if (i<=2) {
				dp[i] = i;
			}else {
				dp[i] = dp[i-1]+dp[i-2];
			}
		}
		System.out.println(dp[n]);		
	}
}
           

01背包

1. 题目：有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
2. 测试案例 capacity=20，N=5， W={2,3,4,5,9}，V={3,4,5,8,10}

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("请输入背包容器:");
		int capacity = sc.nextInt();
		System.out.print("请输入物品个数N:");
		int N = sc.nextInt();
		System.out.print("请输入每个物品的重量:");
		int[] W = new int[N];
		for (int i = 0; i < N; i++) {
			W[i] = sc.nextInt();
		}
		System.out.print("请输入每个物品的价值:");
		int[] V = new int[N];
		for (int i = 0; i < N; i++) {
			V[i] = sc.nextInt();
		}

		int packageHandle = packageHandle(capacity,N,W,V);
		System.out.println(packageHandle);
	}
	// 01背包处理
	public static int packageHandle(int capacity,int N,int[] W,int[] V) {
		int max = 0;// 最多装载物品的重量
		int[][] dp = new int[N+1][capacity+1];
		for (int j = 0; j < N; j++) {// 第一个物品数组开始为0，单独处理
			if (W[0] > j) {
				dp[0][j] = 0;
			}else {
				dp[0][j] = V[0];
			}
		}
		for (int i = 1; i < N; i++) {
			for (int j = 0; j <= capacity; j++) {
				if (W[i]>j) {//如果物品重量大于剩余重量
						dp[i][j] = dp[i-1][j];
				}else {
					dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-W[i]] + V[i]);
				}
//				max = Math.max(max, dp[i][j]);
			}
		}
		return dp[N-1][capacity];
	}
           

1. 对空间进行优化(将二维数组优化维一维数值)
   • dp找的是前一个状态，二维数组刚好可以将前一个状态表现在dp[i-1[j]中，但这样用了二维数组对空间就不太节约了，所以我们要优化成一维数组所以就需要将前一个状态弄到一维数组中即找没有更新的状态，所以我们可以逆序来找
   • 也就是说将j=n背包容量从最大开始找向前找状态，前面的状态都还没有更新所以就可以继续用一维数组每次都在一维数组中找到前一个状态。而如果是按递增的顺序去的化每次j-w[i]都是找到了更新后的状态，我们要找的上一个状态，而不是更新后的状态

public static int opHandle(int capacity,int N,int[] W,int[] V) {
			int[] f = new int[capacity+1];
			for (int i = 0; i < N; i++) {
				for (int j = capacity; j >=W[i]; j--) {
					f[j] = Math.max(f[j],f[j-W[i]] + V[i]);
				}
			}
			return f[capacity];
		}