动态规划算法基础及leetcode例题
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];
}
}