动态规划学习记录（自用）

一、适用范围

当问题可分解为相互独立的子问题时，考虑动态规划。例如：斐波那契数列、爬楼梯问题、最值问题、背包问题等。

二、动态规划经典题型

1、最简单的爬楼梯问题

力扣链接

问题描述：

假设爬 n 阶楼梯，每次可以爬 1 或 2 个台阶，有多少种不同的爬楼方法？

思路：

要到n阶，只能从n-1阶或n-2阶上来，因此定义dp[i]表示爬到i阶对应的方法数，状态转移方程即为dp[i]=dp[i-1]+dp[i-2]。接下来需要判断边界值：根据状态转移方程，显然i>=2。因此初步确定边界值为dp[0]=0,dp[1]=1,此时代入状态转移方程得dp[2]=0+1=1。根据实际情况，要到2阶楼梯，要么一次爬2阶，要么一次爬1阶爬2次，共有两种方法。因此dp[2]也是边界值。

核心算法：

int[] dp=new int[n+1];//dp[i]表示爬到i阶的方法数。
if n<=2:return n;
else://dp[0]用不到，不需要赋值，默认为0
    for i=3,i<=n:
      dp[i]=dp[i-1]+dp[i-2];
    return dp[n];

代码：

public static int climbStairs(int n) {
   
    
		int res=0;
		int[]dp=new int[n+1];
		dp[0]=0;
		dp[1]=1;
		if(n>=2) {
   
    
			dp[2]=2;
			for(int i=3;i<=n;i++) {
   
    
				dp[i]=dp[i-1]+dp[i-2];
			}
		}
		res=dp[n];
		return res;
	}

爬楼问题推广一：爬楼途径不定

问题描述：
假设爬 n 阶楼梯，climbs数组存放一次爬几阶楼梯，默认不重复，有多少种不同的爬楼方法？例：输入：n=4，climbs={1,2,3} 输出：7

思路：
本题是原爬楼问题的扩展，相当于climbs中只有两个元素1和2。对于本题，解题思想与上述爬楼问题一致。要到n阶，只能从n-climbs[j]阶上来，因此需要遍历climbs数组。定义dp[i]表示爬到i阶对应的方法数，状态转移方程即为dp[i]=dp[i-climbs[0]]+dp[i-climbs[1]]+…+dp[i-climbs[len-1]]。接下来需要求边界值：dp[0]=0。需要注意的是，当状态转移方程中存在dp[0]时，需要加1。参见核心算法。
核心算法：

int[]dp=new int[n+1];
dp[0]=0;
for i=1,i<=n:
    for j=0,j<climbs.length:
        if i-climbs[j]==0:
            dp[i]=dp[i]+dp[i-climbs[j]]+1;//状态转移方程中存在dp[0]时，需要加1
        else if i-climbs[j]>0://不考虑小于0的情况，小于0说明不存在合法组合
            dp[i]=dp[i]+dp[i-climbs[j]];
return dp[n];

代码：

public static int climbStairs(int[]climbs,int n) {
   
    
    	int res=0;
    	int[]dp=new int[n+1];
    	dp[0]=0;
    	for(int i=1;i<=n;i++) {
   
    
    		for(int j=0;j<climbs.length;j++) {
   
    
    			if(i-climbs[j]==0) {
   
    
    				dp[i]=dp[i]+dp[i-climbs[j]]+1;
//当存在dp[0]时，相当于从0阶一次跳i阶到达目的地，只有一种跳法。而dp[0]=0,故需加1
    			}
    			else if(i-climbs[j]>0) {
   
    
    				dp[i]=dp[i]+dp[i-climbs[j]];
    			}			
    		}	
    	}
    	res=dp[n];
    	return res;
    }

爬楼问题推广二：零钱问题之不同组合数

力扣链接
力扣题解
问题描述：

给定amount代表金额，coins数组存放零钱，假设每种零钱有无限个，求兑换amount的组合数。若不存在返回0。例如：输入：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章节背包问题），即将不同面额的硬币放到总金额为n的包里，求刚好装满包的组合数。
定义dp[i][j]表示前i个硬币组成金额j的组合数。
（1）若第i个硬币面额大于j，则第i个硬币不能放进包中，此时dp[i][j]=dp[i-1][j]；
（2）若第i个硬币面额小于等于j，则第i个硬币能放进包中，此时有k+1种选择：不放，放0个，放1个，…放k个，假设放k个硬币i，首先需判断ki是否小于等于j，若等于，此时的组合数应为dp[i-1][j-ki]*1，将以上k+1种选择对应的组合数相加即为dp[i][j]的值，故dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]])；
边界值：dp[i][0]=1;dp[0][0]=1;dp[0][1~amount]=0（力扣题目用例测试时要求dp[i][0]=1）。
代码：

public static int coinChange(int[] coins, int amount) {
   
    
		int res=0;
		int[][]dp=new int[coins.length+1][amount+1];
		for(int m=0;m<coins.length+1;m++) {
   
    
			dp[m][0]=1;
		}
		for(int i=1;i<=coins.length;i++) {
   
    
			for(int j=1;j<=amount;j++) {
   
    
				if(j>=coins[i-1]) {
   
    
					dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
				}
				else {
   
    
					dp[i][j]=dp[i-1][j];
				}
			}	
		}
		res=dp[coins.length][amount];
		return res;
	}

2、背包问题

一文搞懂背包问题题解

2.1 0-1背包问题

问题描述：
给定int数组weights存放物品重量，int数组values存放物品价值，n存放包的容量，求装入背包的物品的最大价值。每个物品只能放0次或1次。
思路：

定义dp[i][j]表示前 i 件物品放入一个容量为 j 的背包可以获得的最大价值（每件物品最多放一次）,则可能有以下两种情况：
（1）第i件物品不能放进包中，即第i件物品的重量大于j【注1】，超重了，此时只能将前i-1件物品放进容量为j的包中，dp[i][j]相当于将前i-1件物品放进容量为j的包中可以获得的最大价值，故有：dp[i][j]=dp[i-1][j]；
（2）第i件物品能放进包中，即第i件物品的重量小于等于j，此时有两种选择【注2】，要么放要么不放。若放，此时dp[i][j]相当于将前i-1件物品放进容量为j-w(i)的包中可以获得的最大价值加上第i件物品的价值（w(i)表示第i件物品的重量，v(i)表示第i件物品的价值），故有：dp[i][j]=dp[i-1][j-w(i)]+v(i)。若不放，则有dp[i][j]=dp[i-1][j]。需要取这两种选择中的最大值。即dp[i][j]=max(dp[i-1][j-w(i)]+v(i),dp[i-1][j])。
注1：为什么判断第i件物品的重量与j的关系，而不是前i件物品的重量和与j的关系？因为本质上是看第i件物品能不能放到包里，可以只放第i件物品然后根据状态转移方程求最大价值，不需要考虑前i-1件物品。在纸上举个实例求dp数组的值就能理解了。
注2：因为物品是有重量的，有可能第i件物品重量特别大，而价值特别小，这时候不放第i件物品价值更大。例如包容量为10时，一个物品重量等于10，而价值只有1，其他物品重量为1，而每个物品价值都为10，显然此时不放重量为10的物品能得到的价值更高。
核心算法：

int[][]dp=new int[weights.length+1][n+1];
//边界值
for p<=weights.length:dp[p][0]=0;
for q<=n:dp[0][q]=0;
//状态转移方程
for i=1;i<=weights.length:
    for j=1;j<=n:
        if weights[i-1]<=j:
            dp[i][j]=max(dp[i-1][j-w(i)]+v(i),dp[i-1][j]);
        else:
            dp[i][j]=dp[i-1][j];
return dp[weights.length][n];

代码：

public static int bags(int[]weights,int[]values,int n) {
   
    
		int res=0;
		int len=weights.length;
		int[][]dp=new int[len+1][n+1];
		//边界值
		for(int p=0;p<=len;p++) {
   
    
			dp[p][0]=0;
		}
		for(int q=0;q<=n;q++) {
   
    
			dp[0][q]=0;
		}
		//状态转移方程
		for(int i=1;i<=len;i++) {
   
    
			for(int j=1;j<=n;j++) {
   
    
				if(weights[i-1]<=j) {
   
    
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1]);
				}
				else {
   
    
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		res=dp[len][n];
		return res;
	}

2.2 完全背包问题

问题描述：
给定int数组weights存放物品重量，int数组values存放物品价值，n存放包的容量，求装入背包的物品的最大价值。每个物品能放无限次。

思路：
类似于0-1背包问题，区别在于此时的第i件物品并非只有放和不放两种选择，而是有不放、放1件、放2件…放k件共k+1种选择，因此可能有以下两种情况：
（1）第i件物品不能放进包中，即第i件物品的重量大于j，超重了，此时只能将前i-1件物品放进容量为j的包中，dp[i][j]相当于将前i-1件物品放进容量为j的包中可以获得的最大价值，故有：dp[i][j]=dp[i-1][j]；
（2）第i件物品能放进包中，即第i件物品的重量小于等于j，此时有k+1种选择：不放、放1件、放2件…放k件。若不放，则有dp[i][j]=dp[i-1][j]。若放，需要判断放k件物品i是否会超重，即比较kw(i)与j的关系，对应的，dp[i][j]=dp[i-1][j-kw(i)]+kv(i)
（w(i)表示第i件物品的重量，v(i)表示第i件物品的价值）。需要取这k+1种选择中的最大值。即dp[i][j]=max(dp[i-1][j],dp[i-1][j-w(i)]+v(i),dp[i-1][j-2w(i)]+2v(i),…dp[i-1][j-kw(i)]+kv(i)) 记为①式。由于dp[i][j-w(i)]=max(dp[i-1][j-w(i)],dp[i-1][j-2w(i)]+v(i),dp[i-1][j-3w(i)]+2v(i),…dp[i-1][j-k*w(i)]+(k-1)*v(i)) 记为②式，将②式代入①式得，dp[i][j]=max(dp[i-1][j],dp[i][j-w(i)]+v(i)），此为优化后的完全背包的状态转移方程。

代码：

public static int bags(int[]weights,int[]values,int n) {
   
    
		int res=0;
		int len=weights.length;
		int[][]dp=new int[len+1][n+1];
		for(int p=0;p<=len;p++) {
   
    
			dp[p][0]=0;
		}
		for(int q=0;q<=n;q++) {
   
    
			dp[0][q]=0;
		}
		//
		for(int i=1;i<=len;i++) {
   
    
			for(int j=1;j<=n;j++) {
   
    
				if(weights[i-1]<=j) {
   
    				
					//与0-1背包问题只有这一行代码的区别
					dp[i][j]=Math.max(dp[i-1][j], dp[i][j-weights[i-1]]+values[i-1]);			
				}
				else {
   
    
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		res=dp[len][n];
		return res;
	}

2.3 背包问题的特殊说明

以上讨论的背包问题默认要求不超过背包容量，直接将所有值初始为0即可，即所有背包一定存在一个合法解：背包中什么都不放时价值为0。它虽然不是最优解，没有满足背包中物品价值最大，但属于一个合法解。
但还存在另一种背包问题，即要求恰好装满背包。此时的合法解必须满足恰好装满背包，否则即使价值最大，也是无效解。显然只有dp[i][0]=0是合法解，其他的dp值必须由合法解推出，因此其他dp值全部赋为无穷大或无穷小。

2.4 背包问题实例–查找充电设备组合（华为机试真题）

问题描述：
给定充电设备数n，最大输出功率maxPower，int数组存放充电设备的功率，输出最优元素。假设任意个充电设备（不需要连续）的功率总和，为p的一个元素，p中最接近最大输出功率的为最优元素（小于等于最大输出功率），不存在最优元素则输出0。示例：输入n=4 ，powers={50 20 10 60} ，maxPower=90，输出：90。
思路：
本题属于0-1背包，相当于将不同价值的物品（功率数组对应价值数组）放进容量为maxPower的包中，求最大价值。定义dp[i][j]表示前i件物品放进容量为j的包中的最大价值，则有：
（1）若powers[i-1]>j，说明第i件物品不能放进包中，此时dp[i][j]=dp[i-1][j]；
（2）若powers[i-1]<=j，说明第i件物品能放进包中，此时可选择放或者不放，若不放，dp[i][j]=dp[i-1][j]；若放，dp[i][j]=dp[i-1][j-powers[i-1]]+powers[i-1]；
边界值默认为0，不需特别处理。
代码：

public static int maxOutputPower(int n,String str,int maxPower) {
   
    
		int res=0;
		int[]powers=new int[n];
		String[] st=str.split(" ");
		for(int k=0;k<n;k++) {
   
    
			powers[k]=Integer.parseInt(st[k]);
		}
		int[][]dp=new int[n+1][maxPower+1];
		
		for(int i=1;i<=n;i++) {
   
    //{50 20 10 60}  90
			for(int j=1;j<=maxPower;j++) {
   
    
				if(powers[i-1]>j) {
   
    
					dp[i][j]=dp[i-1][j];
				}
				else {
   
    
					dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-powers[i-1]]+powers[i-1]);
				}
			}
		}
		res=dp[n][maxPower];
		return res;
	}

3、零钱问题之最少货币数

力扣链接

问题描述：

给定amount代表金额，coins数组存放零钱，假设每种零钱有无限个，求兑换amount的最少货币数。若无法兑换返回-1。例如：输入：amount=11，coins={1,2,5} 输出：3

解法一：二维dp

思路：
本题可当作完全背包处理，相当于将不同面额的零钱（coins数组对应价值数组）放进容量为amount的包中，求恰好装满的最少货币数。定义dp[i][j]表示前i种货币放进容量j的包中恰好装满的最少货币数，则有：
（1）若coins[i-1]>j，说明第i件物品不能放进包中，此时dp[i][j]=dp[i-1][j]；
（2）若coins[i-1]<=j，说明第i件物品能放进包中，此时有k+1种选择，若不放，dp[i][j]=dp[i-1][j]；若放k个货币，dp[i][j]=dp[i-1][j-kcoins[i-1]]+1k；需要取这k+1种选择中的最小值，可优化为dp[i][j]=min(dp[i-1][j]，dp[i][j-coins[i-1]]]+1)。
由于本题要求恰好装满，因此需要关注边界值。令dp[i][0]=0，其他所有值赋为无穷大。

代码：

public static int coinChange(int[] coins, int amount) {
   
    
		int res=0;
		int[][]dp=new int[coins.length+1][amount+1];
		//边界值
//		double dmax = Double.POSITIVE_INFINITY;  // 1.0 / 0.0, 正无穷大
//		int imax=(int)dmax;
		for(int k=0;k<=coins.length;k++) {
   
    
			dp[k][0]=0;
			for(int p=1;p<=amount;p++) {
   
    
				dp[k][p]=0x3f3f3f3f;
			}
		}
		//状态转移方程
		for(int i=1;i<=coins.length;i++) {
   
    
			for(int j=1;j<=amount;j++) {
   
    
				if(coins[i-1]>j) {
   
    
					dp[i][j]