【Java】我所知道的十大常用算法之动态规划（斐波那契、妈妈找零钱、小明选物品）
前言需求
本篇学习了解新的算法：动态规划" title="动态规划">动态规划算法" title="动态规划算法">动态规划算法，在我们生活中有很多事情可以涉及到
一、什么是动态规划算法
生活问题介绍
假设您是个土豪，身上携带十张钞票，分别是的1、5、10、20、50、100元面值
我们的问题是：请你用最少的钞票组合最大的金额
根据我们的生活经验，显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推
在这种策略下，我们十张的钞票分配是：666 = 6×100 + 1×50 + 1×10 + 1×5 + 1×1
这种策略叫贪心，指在对问题进行求解的时候，每一步都采用最好或者最优的选择，贪心会尽快让我们求值金额变得更小
不同情况的问题所在
但是我们更换另一组面额的钞票组时，贪心的策略也许就不会成立了。
比如说面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错
贪心的方法：凑15 = 1 × 11 + 4 × 1（使用了5张钞票）
我们的方法：凑15 = 3 × 5 （只用3张钞票）
为什么会这样呢？贪心策略错在了哪里？答案是：鼠目寸光
刚刚我们提到贪心策略的纲领是：“尽量使接下来面对的求值金额更小”。
在凑15的局面时，会优先使用11来把接下来的求值金额降到4；
但是在这个问题中，凑出4的代价是很高的，必须使用4×1。
如果使用了5，剩下的求值金额会降为10，没有4那么小，但是凑出10只它需要两张5元。
怎么样避免情况问题？
我们重新分析凑出15块的情况：
1.我们如果取11（1 x 11），接下来就面对凑4的情况（4 x 1）
2.我们如果取5（1 x 5），则接下来面对凑10的情况（5 x 2）
我们接下来使用f(n)来表示凑出n所需的最少钞票数量
1、凑1块使用 f(1) = 1 ，1面额使用1张
2、凑4块使用 f(4) = 4 ，1面额使用4张
3、凑5块使用 f(5) = 1 ，5面额使用1张
4、凑10块使用 f(10) = 2 ，5面额使用2张
5、凑14块使用 f(14) = 4 ，11面额使用1张、1面额使用3张
显然我们如果凑15块的话，就有几种方式了
1、凑15块使用 f(15) = f(4) + f(11) ，11面额使用1张、1面额使用4张
2、凑15块使用 f(15) = f(10) + f(5) ，5面额使用1张、5面额使用2张
3、凑15块使用 f(15) = f(14) + f(1) ，5面额使用2张1面额使用2张、1面额使用1张
那么，如果我们以 11 为主，最后的代价（用掉的钞票总数）是多少呢？
明显cost = f(4) + 1 = 4 + 1 = 5，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。
依次类推，马上可以知道：如果我们用5来凑出15，cost就是f(10) + 1 = 2 + 1 = 3
这样我们显而易见，cost值最低的是取5的方案。我们通过上面式子，做出了正确的决策！
这给了我们一个至关重要的启示:fn 与f(n-1)，f(n-5),f(n-11)相关
简单的来说公式 = fn = min{f(n - 1)，f(n-5)，f(n-11)} + 1
这种方式会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！
我们要求出f(15)，只需要知道f(14),f(10),f(4)的值。这样干，取决于问题的性质：求出f(n)，只需要知道几个更小的f(c)。我们将求解f(c)称作求解f(n)的“子问题”。
这就是DP（动态规划，dynamic programming）.
将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。
二、通过斐波那契数列来初识思想
如果对于斐波那契还是很懂的小伙伴可以多看看我之前的文章：斐波那契数列
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
让我们根据示例回顾一下斐波那契数列的特点与之前的计算方法
long one = 0;public int fibOne(int N) {
one++;
if (N <= 1) {
return N;
}
return fibOne(N-1) + fibOne(N-2);//*****递归
}
我们看第一个式子：递归，反复调用自身函数，它的时间复杂度 O(2^N)，空间复杂度O(N)
但是计算中函数被大量调用容易造成内存溢出【StackOverflowError】
当我输入N = 2 时，F(2) = F(1) + F(0)，执行步数：3
这时有小伙伴就会好奇，这个步数为什么是3？，因为进来方法就会one ++
好像还能承受，执行有点少，那么但我输入N = 10、20、30的时，我们看看
public static void main(String[] args) {System.out.println(fibOne(10)+" - 执行次数one : "+one);
System.out.println(fibOne(20)+" - 执行次数one : "+one);
System.out.println(fibOne(30)+" - 执行次数one : "+one);
}
运行结果如下：
55 - 执行次数one : 177
6765 - 执行次数one : 22068
832040 - 执行次数one : 2714605
顿时一下就不好了，执行步数那么多，所以就很多情况下造成内存泄露。
互动问题
那么当我输入N = 3时、N=4时、执行的步数是多少呢？为什么呢？
各位小伙伴可以在下方评论告诉我答案噢
// 递归// 记忆化 自顶向下 | 从后往前 的方法 我们先计算存储子问题的答案，然后利用子问题的答案计算当前斐波那契数的答案。
// 我们将递归计算，但是通过记忆化不重复计算已计算的值。
// 时间复杂度 O(N) 空间复杂度O(N) 需要一个大小N的数组
long two = 0;
private Integer[] dp;
public int fibTwo(int N) {
dp = new Integer[N + 1];
if (N <= 1) {
return N;
}
dp[0] = 0;
dp[1] = 1;
return memoizeTwo(N);
}
public int memoizeTwo(int N) {
two++;
if (dp[N] != null) {
return dp[N];
}
dp[N] = memoizeTwo(N-1) + memoizeTwo(N-2);//*****递归
//同时 进行了记录在数组中 【记忆化的递归】
return memoizeTwo(N);
}
我们上一个递归方法的执行步骤实在是太不友好了，我们需要优化一下
我们采用数组的方式记录每个递归结果
这样我们保存后，则无需再做重复的事情，我们可以测试看看差距
public static void main(String[] args) {System.out.println(fibTwo(10)+" - 执行次数one : "+two);
System.out.println(fibTwo(20)+" - 执行次数one : "+two);
System.out.println(fibTwo(30)+" - 执行次数one : "+two);
}
运行结果如下：
55 - 次数two : 28
6765 - 次数two : 86
832040 - 次数two : 174
我看对比的结果，差距一下就出来。这是典型空间换时间优化
若我们采用完全堆的方式即O(2^N -1)即可优化刚刚的代码直接返回
public int memoizeTwo(int N) {two++;
if (dp[N] != null) {
return dp[N];
}
dp[N] = memoizeTwo(N-1) + memoizeTwo(N-2);//*****递归
//同时 进行了记录在数组中 【记忆化的递归】
return dp[N]; // 完全符合 O(2*N-1)
}
public static void main(String[] args) {System.out.println(fibTwo(10)+" - 执行次数one : "+two);
System.out.println(fibTwo(20)+" - 执行次数one : "+two);
System.out.println(fibTwo(30)+" - 执行次数one : "+two);
}
运行结果如下：
55 - 次数two : 19
6765 - 次数two : 58
832040 - 次数two : 117
对比一下，我们现在这个优化的更加的少了一些
三、通过背包问题来加强思想
背包问题分析
1.背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。
其中又分01背包和完全背包(完全背包指的是：每种物品都有无限件可用)
2.有的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
四、背包问题1：妈妈给零花钱
妈妈给你准备了N天的零花钱，你可以任意领取，但是有一个条件: 【不能连续两天都领取】
请问聪明的你怎样领取得到的零花钱最多?
比如 4天： 分别是[1,2,3,1]，最多的钱： 4
解释方案： 第1天(金额 = 1)，第3天(金额 = 3)，总数 = 1 + 3 = 4
比如 5天： 分别是[2,7,9,3,1]，最多的钱： 12
解释方案： 第1天(金额 = 2)，第3天(金额 = 9)，第5天(金额 = 1)，总数 = 2 + 9 + 1 = 12
比如 7天： 分别是[2,8,4,7,10,9,6]，
请问最多的钱： ? 你的解释方案： ???
这里的问题属于完全背包问题，每种物品都可以无限件使用
简单图标思路分析
1.我们可以选择第一天拿2块开始：2、4、10、6
2.我们可以选择第一天不拿，从第二天开始拿8块开始：8、7、9
3.我们可以选择第一天不拿，从第二天开始拿8块开始：8、10、6
// 线性推动public static int robOne(int[] nums) {
int prevMax = 0;
int currMax = 0;
for (int x : nums) {
int temp = currMax;
currMax = Math.max(prevMax + x, currMax);// 推导公式
prevMax = temp;
}
return currMax; // 24 【8 7 9】 【8 10 6】
}
该代码的方式采用PrevMax 与 CurrMax 记录变化进行筛选
当未加载：2 时currMax、PrevMax = 0，加载后currMax=2、PrevMax = 0，选2
当未加载：8 时currMax=2、PrevMax = 0，加载后currMax=8、PrevMax = 2，更改为选8 
当未加载：4 时currMax=8、PrevMax = 2，加载后currMax=8、PrevMax = 8，继续选8 
当未加载：7 时currMax=8、PrevMax = 8，加载后currMax=15、PrevMax = 8，继续选8，7 
当未加载：10 时currMax=15、PrevMax = 8，加载后currMax=18、PrevMax = 15，更改为选8，10
当未加载：9 时currMax=18、PrevMax = 15，加载后currMax=24、PrevMax = 18，更改为选8，7，9
当未加载：6 时currMax=24、PrevMax = 18，加载后currMax=24、PrevMax = 24，可以选8，7，9 与 8，10，6 
五、背包问题2：小明背包选物品
我们小明同学有一个背包，重量容量为4磅，有以下物品需要你帮忙分配
我们小明同学的需求是
1、要求装入的背包的总价值最大，并且重量不超出限制
2、要求装入的物品不能重复
小明同学的图表思路分析
我们使用图表的方式来手动分析筛选一下看看
当只有一把吉他的时候，无论是背包负重0磅、1磅、2磅、3磅、4磅，都只能选择吉他
当有吉他、音响的时候，背包负重0磅、1磅、2磅、3磅，我们只能选择吉他，当背包负重4磅的时候，音响的价值大于吉他，我们选择音响
当有吉他、音响、电脑的时候，背包负重0磅、1磅、2磅，我们只能选择吉他
当背包负重3磅的时候，电脑的价值大于吉他，我们选择电脑当。
背包负重4磅的时候，我们的选择策略有
1.直接选择音响，价值（3000）满足负重
2.直接选择电脑+吉他，价值（3500）满足负重
小明同学代码逻辑思路分析
1.我们设每件物品i，采用w[i]表示负重，v[i]表示价值，当前背包重量j
2.当准备加入新增的商品 i 的重量w[i]大于 前背包的容量 j 时，就直接使用上一个单元格的装入策略：当 w[i] > j 时：v[i][j]=v[i-1][j]
3.当准备加入新增的商品 i 重量w[i]小于等于当前背包的容量 j 时，采用最佳策略：当 j >= w[i] 时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
这个时候，我们肯定会选择音响符合我们的最佳策略，我们接着看下一个
因为我们的思路会使用到上一个单元格，所以我们需要做成的表格图是
这个时候，我们肯定会选择电脑+吉他成为符合我们的最佳策略
public static void main(String[] args) {//我们的商品有
// 1.吉他（重量：1 价值：1500）、
// 2.音响（重量：4 价值：3000）、
// 3.电脑（重量：3 价值：2000）、
int [] w = {1,4,3};//代表重量
int [] val = {1500,3000,2000};//代表价值
int m = 4;//代表背包最大负重
int n = val.length;//代表商品个数
//创建二维数组
//n +1 代表多一行 m+1 代表多一列
int [][] v = new int[n+1][m+1];
for (int i =0; i <v.length; i++){
for(int j = 0 ; j < v[i].length; j++){
System.out.print(v[i][j] + "\t");
}
System.out.println();
}
}
运行结果如下：
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
接下来我们按照思路执行动态规划的代码
System.out.println("开始使用动态规划来处理问题=========================");for (int i = 1; i <v.length; i++){
for(int j = 1 ; j < v[i].length; j++){
if(w[i - 1 ]>j){
v[i][j] = v[i - 1][j];
}else{
v[i][j] = Math.max(v[i - 1 ][j],val[i - 1 ] + v[i-1][j-w[i -1]]);
}
}
}
for (int i =0; i <v.length; i++){
for(int j = 0 ; j < v[i].length; j++){
System.out.print(v[i][j] + "t");
}
System.out.println();
}
运行结果如下：
开始使用动态规划来处理问题=========================
0 0 0 0 0
0 1500 1500 1500 1500
0 1500 1500 1500 3000
0 1500 1500 2000 3500
当然这只是按照思路来显示的表格，但是我们需要显示具体购买哪些商品
那么我们的思路是什么呢？
1.根据公式将使用新的二维数组记录商品的存放记录
2.若w[i - 1 ]>j 则采用v[i][j]=v[i-1][j]的方式不记录
3.若j >= w[i]，则采用v[i]+v[i-1][j-w[i]]的方式记录标志为1
//记录商品存放情况，定制一个二维数组int[][] path = new int[n+1][m+1];
for (int i = 1; i <v.length; i++){
for(int j = 1 ; j < v[i].length; j++){
if(w[i-1]>j){
v[i][j] = v[i - 1][j];
}else{
// v[i][j] = Math.max(v[i - 1 ][j],val[i - 1 ] + v[i-1][j-w[i -1]]);
//将Max函数里面的两个值采用if-else的方式进行判断操作
if(v[i-1][j] < val[i-1] + v[i-1][j-w[i -1]]){
v[i][j] = val[i-1] + v[i-1][j-w[i -1]];
path[i][j] = 1;
}else{
v[i][j] = v[i - 1 ][j];
}
}
}
}
for (int i =0; i <path.length; i++){for(int j = 0 ; j < path[i].length; j++){
System.out.print(path[i][j] + "t");
}
System.out.println();
}
运行结果如下：
0 0 0 0 0
0 1 1 1 1
0 0 0 0 1
0 0 0 1 1
这个时候我们在将标志为1的输出出来看看
System.out.println("==================================================");int i = path.length - 1 ; //行的最大下标
int j = path[0].length -1;//列的最大下标
while(i>0 && j>0){
if(path[i][j] == 1){
System.out.printf("第%d个商品放入到背包n",i);
j-= w[i-1];
}
i--;
}
运行结果如下：
第3个商品放入到背包
第1个商品放入到背包
以上是 【Java】我所知道的十大常用算法之动态规划（斐波那契、妈妈找零钱、小明选物品） 的全部内容， 来源链接： utcz.com/a/91371.html
