最近在代码随想录（代码随想录）刷了一些有关动态规划的算法题，收获还蛮大的，下面是我的一些学习心得分享，不足之处敬请批评指正~
首先来简单介绍一下什么是动态规划以及动规与贪心有何区别？
动态规划（Dynamic Programming），简称DP，用以解决有很多重叠子问题的问题。
比如说：最经典的0-1背包问题：给你一些有不同重量和不同价值的物品，而你的背包大小是固定的，问你挑选哪些物品能使得你背包内所装物品的价值最高。
动态规划问题中每一个状态一定是由上一个状态推导出来的，在这一点上区别于贪心算法，贪心算法是从局部直接选取最优解，并不依赖于之前计算出来的状态。
动态规划的题型可以分为几类：（我暂时只刷到了完全背包问题）
·一些基础问题（斐波那契数列、不同路径、整数拆分等）
·经典的0-1背包问题及一些变种问题
·完全背包问题及一些变种问题
0-1背包和完全背包有何区别呢？
0-1背包是每件物品仅能取一次不可重复取，完全背包是每件物品不限数量可以随便取
动态规划类问题的一般解题步骤如下：
- 确定dp[]数组及其下标的含义
- 确定递推公式
- dp[]数组的初始化（就问题不同，初始化方法也不同）
- 确定遍历顺序
- 举例推导dp数组（即自检的过程）
下面我以一道经典的整数拆分问题为例演示上述过程:力扣
给定一个正整数
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。
下面直接以代码说明问题:
class Solution {
//整数拆分问题
public int integerBreak(int n) {
//定义dp数组，明确数组中每个元素的含义:dp[i]表示将i拆分后所得乘积的最大值
//数组长度一般定义为n+1，因为我们想要的结果就是dp[n]
int[] dp = new int[n + 1];
//初始化dp数组，值为2时，所得最大拆分结果为1，因为值为0或1时的初始化没有意义所以在这里就不初始化了
dp[2] = 1;
//外层循环
for (int i = 3; i <= n; i++) {
//内层循环
for (int j = 1; j < i - 1; j++) {
//递推公式，dp[i]用以在每次循环时和之前的值进行比较，(i-j)*j表示为拆成两个数所得乘积
//j*dp[i-j]表示将i拆分成两个及两个以上所得乘积(利用之前计算结果),递归顺序为从前到后
//递推公式不太理解的同学自己在草稿纸上推导一下就明白了
dp[i] = Math.max(dp[i], Math.max((i - j) * j, j * dp[i - j]));
}
}
//返回结果
return dp[n];
}
}相信大家已经对动归有了一些认识，接下来我们来看看经典的0-1背包问题:
0-1背包问题提前敲小黑板：0-1背包问题要注意的点是外层循环和内层循环的遍历顺序有n件物品和一个最多能背重量为w 的背包。
第i件物品的重量是weight[i]，得到的价值是value[i] 。
每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
下面以代码说明问题:
public class packBag {
public static void testWeightBagProblem(int[] weight, int[] value, int size) {
int wLen = weight.length;
//定义dp数组，dp[j]表示背包容量为j时能获得的最大价值
int[] dp = new int[size + 1];
//遍历顺序：先遍历物品再遍历背包容量
for (int i = 0; i < wLen; i++) {
//倒序遍历商品容量,防止物品被重复放入i
//一维数组必须先遍历商品再遍历背包容量
//这里的终止条件为j>=weight[i]，防止为装不下的物品初始化,且防止下标越界
for (int j = size; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//打印dp数组
for (int i = 0; i <= size; i++) {
System.out.print(dp[i] + " ");
}
}
}下面是0-1背包的经典的变种问题-统计满足条件的组合个数：
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。
现在你有两个符号 + 和 -。
对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3一共有5种方法让最终目标和为3。
直接上代码：
public static int findTargetSumWays(int[] nums, int target) {
//数学推导
//left + right = sum
//left - right = target
//left = (sum + target) / 2
//如果sum + target的和不为偶数则无解
int sum = 0;
for (int i = 0; i < nums.length; i++) sum += nums[i];
if (Math.abs(target) > sum) return 0;
if ((target + sum) % 2 != 0) return 0;
int size = (target + sum) / 2;
//dp数组的定义：dp[j]表示:和为j的组合有多少种
//找出和为size的组合的个数即dp[size]
int[] dp = new int[size + 1];
dp[0] = 1;
//依然是先遍历商品后遍历背包容量
for (int i = 0; i < nums.length; i++) {
for (int j = size; j >= nums[i]; j--) {
//这里是重点！！！！
dp[j] += dp[j - nums[i]];
}
}
return dp[size];
}下面我们进行一个总结：
1.0-1背包问题中最重要的点是弄清楚背包容量是多少，物品是哪些，实际问题中可能不会直接告诉你这些信息，我们要能从题干中分析出来
2.其次，我们要注意遍历顺序为先遍历物品后遍历背包容量
3.最后，我们要注意题目中要统计的是有关最大价值类问题还是组合数的问题。
如果是最大价值类问题递推公式就是：
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);如果是组合数的问题递推公式就是：
dp[j] += dp[j - nums[i]];再次提前敲响小黑板：要关注代码中内层循环的遍历顺序问题和递推公式问题以及区分组合问题和排列问题有N件物品和一个最多能背重量为W的背包。
第i件物品的重量是weight[i]，得到的价值是value[i] 。
每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
依旧以代码说明问题：
public class CompletePack {
public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
//遍历物品
for (int i = 0; i < weight.length; i++) {
//注意这里，如果是完全背包问题就是从前到后遍历背包容量
for (int j = weight[i]; j <= bagWeight; j++) {
//递推公式和0-1背包相同
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
System.out.println(dp[bagWeight]);
}
}
下面是完全背包问题的变种问题：
给定不同面额的硬币和一个总金额。
写出函数来计算可以凑成总金额的硬币组合数。
假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
示例 3: 输入: amount = 10, coins = [10] 输出: 1
这道题就是很明显的完全背包的组合问题，直接上代码:
public int change(int amount, int[] coins) {
int len = coins.length;
//定义dp数组,大小为背包容量大小->amount
//dp[i]表示背包容量为i时的组合数
int[] dp = new int[amount + 1];
//初始化
dp[0] = 1;
//先遍历商品，再遍历背包容量
for (int i = 0; i < len; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}其实这个问题就是将组合问题的递推公式和完全背包问题的内层循环的遍历顺序相结合
再来一道有关完全背包的排序问题：
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3] target = 4
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
这道题要区分相同组合的不同排列问题，直接上代码:
排列问题和组合问题的最大区别是：排列问题要先遍历背包容量再遍历物品！！！ public int combinationSum4(int[] nums, int target) {
//求排列就要先遍历背包容量后遍历商品
int len = nums.length;
int[] dp = new int[target + 1];
//dp数组初始化
dp[0] = 1;
//注意这里，如果是排列问题就要先遍历背包容量，再遍历物品！！！
for (int i = 0; i <= target; i++) {
for (int j = 0; j < len; j++) {
if (i >= nums[j])
//递推公式依旧没有区别-求数量的递推公式
dp[i] += dp[i - nums[j]];
}
}
return dp[target];
}最后再来分享一道题力扣
给定不同面额的硬币 coins 和一个总金额 amount。
编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
示例 2： 输入：coins = [2], amount = 3 输出：-1
示例 3： 输入：coins = [1], amount = 0 输出：0
示例 4： 输入：coins = [1], amount = 1 输出：1
示例 5： 输入：coins = [1], amount = 2 输出：2
这道题其实是完全背包问题和0-1背包问题中求最大价值类问题的结合体
直接上代码进行分析：
public static int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
//dp[i]表示背包容量为i所需物品的最少个数为dp[i]
int[] dp = new int[amount + 1];
//dp数组初始化为最大值
for (int i = 0; i < dp.length; i++) {
dp[i] = max;
}
//当金额为0时需要的硬币数目为0
dp[0] = 0;
//可以把需要的硬币数量看作背包的价值，求最少的硬币数量即为最小价值
//每一枚硬币的价值为1（默认）
//组合问题先遍历物品
for (int i = 0; i < coins.length; i++) {
//完全背包问题，为正序遍历
for (int j = coins[i]; j <= amount; j++) {
if (dp[j - coins[i]] != max)
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
//判断，如果没有硬币的组合满足amount，则返回-1
return dp[amount] == max ? -1 : dp[amount];
}总结：遇到一道动归问题时：
1.首先要分析该题是0-1背包还是完全背包，这决定了内层循环的遍历顺序是从前到后还是从后到前。
2.其次，判断该问题是组合问题还是排列问题，这决定了内层循环和外层循环的遍历顺序。
3.最后判断该问题是最大值类问题还是数量问题，这决定了递推公式的选择。
最最最重要的是能将你面对的问题合理的转化为背包问题，对应到你的背包容量和你的物品重量和价值，如此才能套用公式算出答案！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）