01 基础理论
题型:动规基础(斐波那契数列or爬楼梯);背包问题;打家劫舍;股票问题;子序列问题
动规误区:只要看懂递推就ok(递推公式只是一部分)
解决动态规划应该要思考的几步:
- 状态转移的DP数组以及下标的含义
- 递推公式
- DP数组为何初始化
- 遍历顺序
- 打印DP数组
02 例题
基础题目
509.斐波那契数列
思路:
确定dp[i]含义:第i个斐波那契数值
递推公式:dp[i]=dp[i-1]+dp[i-2]
dp数组如何初始化:dp[0]=1,dp[1]=1
遍历顺序:从前向后
打印dp数组:为了debug,如果出错,打印检查输出数组;
java代码:
class Solution {
public int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int index = 2; index <= n; index++){
dp[index] = dp[index - 1] + dp[index - 2];
}
return dp[n];
}
}
70. 爬楼梯
思路:
1阶 1种
2阶 2种
3阶 3种(1+2)【1阶的方法+2步就是3阶;2阶的方法+1步就到3阶】
4阶 5种(2+3)【2阶的方法+2步就是3阶;3阶的方法+1步就到3阶】
.....
找到了递推关系:依赖与前两个状态
java代码
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
背包问题
01背包、完全背包、多重背包
01背包
二维dp实现01背包:
一维dp数组实现01背包:
416. 分割等和子集
思路:子集为所有元素之和的一半
容量为[所有元素之和的一半]的背包,抽象为01背包问题
dp[j]的含义:容量为j的背包,所背的最大价值
目标:dp[target]=target【每个元素的数组就是它的重量,也是它的价值】
递推公式:dp[j]=max(dp[j],dp(j-weight[i])+value[i]);
初始化:dp[0]=0;其他非零数组也等于0
遍历顺序:倒序【先物品,后背包】,因为每个元素只使用一次
java代码:
class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0) return false;
int n = nums.length;
int sum = 0;
for(int num : nums) {
sum += num;
}
//总和为奇数,不能平分
if(sum % 2 != 0) return false;
int target = sum / 2;
int[] dp = new int[target + 1];
for(int i = 0; i < n; i++) {
for(int j = target; j >= nums[i]; j--) {
//物品 i 的重量是 nums[i],其价值也是 nums[i]
dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
}
}
return dp[target] == target;
}
}
完全背包
与0-1背包区别:数据可以重复使用
遍历顺序:正序遍历
正序遍历:
private static void testCompletePack(){
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++){ // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
System.out.print(j + "-" +dp[j]);
System.out.print(" ");
}
System.out.println();
}
}
//输出
1-15 2-30 3-45 4-60
3-45 4-60
4-60
倒序遍历:
for (int i = 0; i < weight.length; i++){ // 遍历物品
for (int j = bagWeight; j >= weight[i]; j--){ // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
System.out.print(j + "-" +dp[j]);
System.out.print(" ");
}
System.out.println();
}
//输出
4-15 3-15 2-15 1-15
4-35 3-20
4-35
518.零钱兑换II
动规五部曲:
dp含义:dp[j] 装满容量为j的背包,有dp[j]种方法【最终要求的:dp[amount]】
递推公式:dp[j]+=dp[j-coins[i]]//装满有多少种方法的递推公式
【dp[j]方法数与前面方法数相关(类似爬楼)】
初始化:dp[0]=1【装满背包为0的方法有一种】,非零下标初始为0
遍历顺序:先物品后背包(组合数);先背包后物品(排列数)
java代码:
class Solution {
public int change(int amount, int[] coins) {
//递推表达式
int[] dp = new int[amount + 1];
//初始化dp数组,表示金额为0时只有一种情况,也就是什么都不装
dp[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
377. 组合总和 Ⅳ
与上一次不同的是:
遍历顺序:先背包后物品(求全排列的个数)
java代码
class Solution {
public int combinationSum4(int[] nums, int target) {
if(nums == null || nums.length==0) return 0;
int[] dp = new int[target+1];
dp[0] = 1;
for(int j=0;j<=target;j++){
for(int i=0;i<nums.length;i++){
if(j>=nums[i]){
dp[j] += dp[j-nums[i]];
}
}
}
return dp[target];
}
}
70. 爬楼梯
核心:排列数
java代码:
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n+1];
int[] nums = new int[]{1,2};
dp[0]=1;
for(int j = 0;j<=n;j++){
for(int i=0;i<nums.length;i++){
if(j>=nums[i]){
dp[j] += dp[j-nums[i]];
}
}
}
return dp[n];
}
}
标签:背包,target,nums,int,算法,遍历,例题,leetcode,dp
From: https://www.cnblogs.com/yunshalee/p/17402952.html