动态规划思路和例题应用
dp实在是用得太多了，这里的例题都不知道怎么举例了。本文主要讲讲思路和步骤，典型的分类有01背包问题，也归纳出一个适合自己的模板。（包括之前写过一点的股票问题，也是dp的典中典系列，后续会接着更新~）
一、动态规划思路步骤
1. 动态规划的定义和区别
-
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
-
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
-
动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
-
但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。
-
2. 动态规划的解题步骤
在dp的典型题目中，状态的转移公式（递推公式）是最重要的，但是并不是唯一需要注意的。一个良好的解题，需要完整的方法。下面总结一种比较好的解题步骤。
-
五步曲：
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组的初始化
- 确定遍历的顺序
- 举例推导出dp数组验证
-
注意事项
-
写dp相关的问题，会在推导的时候出现模糊的情况，这里一定要将dp数组，不如说是
dp[i-1][j-1]代表的含义自己思考一次。 -
写代码之前，将状态转移在dp数组上的具体情况模拟一次，如果存在问题，说明是上述的5步中存在问题，常见的有遍历顺序、初始化、递归公式三部分。
-
遇到问题，其实可以自己先思考这三个方面：
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
-
二、动态规划典型例题
1. 整数拆分
（1）题目说明
-
给定一个正整数
n，将其拆分为k个 正整数 的和（k >= 2），并使这些整数的乘积最大化。 -
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
（2）解答分析
拆分为
k个整数，那究竟是多少个呢？此时可以利用动态规划dp进行分析。下面根据五部曲来试试。
- 确定dp数组的含义和下标的定义
-
dp[i]: 题目最后要求什么？是拆分数字i后得到的k个数的乘积的最大值！ -
所以此时的数组可以设为：拆分数字i，可以得到的最大乘积为
dp[i]。
- 确定递推公式
-
dp[i]最大乘积是怎么得到的呢？其实不难发现，将i进行拆分，实际是从1开始遍历到j,存在两种渠道得到dp[i]- 一个是直接
j*(i-j)得到乘积； - 一个是将
j*dp[i-j]，相当于是拆分了(i-j)，可以不仅仅是两个数，还有可能是之前状态下的多种可能；
- 一个是直接
-
j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。那么从1遍历j，比较(i - j) * j和dp[i - j] * j取最大的。 -
递推公式为：
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
- dp的初始化
-
对严格的dp初始化而言，需要根据刚才的递推公式进行讨论。这里只初始化
dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这就是简单的初始化。
- 确定遍历顺序
-
根据已经推导出来的公式：
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));dp[i]是依靠dp[i-1]的状态，所以遍历i一定是从前向后遍历，先是存在dp[i-j]再有dp[i]
-
所以有这样的遍历顺序：
for (int i = 3; i <= n ; i++) { //初始化从2开始 for (int j = 1; j < i - 1; j++) { dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); } } -
注意 枚举
j的时候，是从1开始的。从0开始的话，那么让拆分一个数拆个0，求最大乘积就没有意义了。-
j的结束条件是j < i - 1，其实j < i也是可以的，不过可以节省一步，例如让j = i - 1，的话，其实在j = 1的时候，这一步就已经拆出来了，重复计算，所以j < i - 1 -
至于
i是从3开始，这样dp[i - j]就是dp[2]，正好可以通过我们初始化的数值求出来。
-
- 举例推导出dp数组
-
当n为10的时候，dp数组里的数值，如下：
（3）具体代码
class Solution {
public int integerBreak(int n) {
//dp[i] 为正整数 i 拆分后的结果的最大乘积
int[] dp = new int[n+1];
dp[2] = 1;
for(int i = 3; i <= n; i++) {
for(int j = 1; j <= i-j; j++) {
// 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
//并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
//j 最大到 i-j,就不会用到 dp[0]与dp[1]
dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
// j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
//而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
}
}
return dp[n];
}
}-
复杂度分析：
-
时间复杂度:
在上述数组的遍历中，当对i进行取值的同时，也维护了j作为最大的乘积值的特征
-
空间复杂度:
通过引入了dp数组，对每个正整数i进行结果的拆分，最坏的情况下可以得到n+1组不同的取值结果，因此此时的空间复杂度为O(n)
-
2. 背包问题
早有耳闻背包问题，这里有关背包和物品之间的关系，可以采用动态规划进行修改判断。
这里简单介绍的是01类型的背包问题
-
介绍：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
-
举个例子：
重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 -
求解背包能背的物品的最大价值是多少？
利用二维dp数组求解
-
确定dp数组的下标和含义
-
使用二维数组，即
dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
-
-
确定递推公式
那么可以有两个方向推出来
dp[i][j]，- 不放物品i：由
dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。) - 放物品i：由
dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]]为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i]（物品i的价值），就是背包放物品i得到的最大价值
所以递归公式：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- 不放物品i：由
-
dp数组如何初始化
-
首先从
dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。 -
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。 -
当
j < weight[0]的时候，dp[0][j]应该是 0，因为背包容量比编号0的物品重量还小。 -
当
j >= weight[0]时，dp[0][j]应该是value[0]，因为背包容量放足够放编号0物品。
-
-
确定遍历顺序
- 给出先遍历物品，然后遍历背包重量的代码，这个好理解一些。
// weight数组的大小 就是物品个数 for(int i = 1; i < weight.size(); i++) { // 遍历物品 for(int j = 0; j <= bagweight; j++) { // 遍历背包容量 if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } }
-
举例推导dp数组
具体代码实现
- 这里给出在IDEA中编写的完整题目代码，其中存在两个类似的函数，分别是二维dp数组和一维dp数组的方法：
import java.util.Scanner;
public class dpBeibao {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int wn=in.nextInt(); //物品的个数，用其重量做分类
int vn=in.nextInt(); //表示物品价值的个数
int bagSize=in.nextInt(); //表示包的最大容量
int[] weight = new int[wn];
for(int i=0;i<wn;i++){
weight[i]=in.nextInt();
}
int[] value = new int[vn];
for(int i=0;i<vn;i++){
value[i]=in.nextInt();
}
// int[] weight={1,3,4};
// int[] value = {15,20,30};
testWeightBagProblem(weight,value,bagSize);
System.out.println("------------------");
testWeightBagProblem_1(weight,value,bagSize);
}
/**
* 动态规划获得结果
* @param weight 物品的重量
* @param value 物品的价值
* @param bagSize 背包的容量
*/
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
// 创建dp数组
int goods = weight.length; // 获取物品的数量
int[][] dp = new int[goods][bagSize + 1];
// 初始化dp数组
// 创建数组后，其中默认的值就是0
for (int j = weight[0]; j <= bagSize; j++) {
dp[0][j] = value[0];
}
// 填充dp数组
for (int i = 1; i < weight.length; i++) {
for (int j = 1; j <= bagSize; j++) {
if (j < weight[i]) {
/*
当前背包的容量都没有当前物品i大的时候，是不放物品i的
那么前i-1个物品能放下的最大价值就是当前情况的最大价值
*/
dp[i][j] = dp[i-1][j];
} else {
/*
当前背包的容量可以放下物品i
那么此时分两种情况：
1、不放物品i
2、放物品i
比较这两种情况下，哪种背包中物品的最大价值最大
*/
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
}
}
}
// 打印dp数组
for (int i = 0; i < goods; i++) {
for (int j = 0; j <= bagSize; j++) {
System.out.print(dp[i][j] + "\t");
}
System.out.println("\n");
}
}
//或者尝试一维数组，直接保存当前的重量和价值的数组即可
public static void testWeightBagProblem_1(int[] weight, int[] value, int bagWeight) {
int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 0; i < wLen; i++) {
for (int j = bagWeight; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//打印dp数组
for (int j = 0; j <= bagWeight; j++) {
System.out.print(dp[j] + " ");
}
System.out.println();
}
/*输入：
3 3 4
1 3 4
15 20 30
*/
}-
最后输出：
-
我们只需要选取的是最后一个就行，也就是选择返回:
System.out.println(dp[goods-1][bagSize]);即可。
