动态规划
动态规划题目一般都是求最 xxx，最大的，最长的 xxxx，通常解法就是穷举所有的答案找到最大的，为了避免暴力的低效率情况，就需要优化下，通过加入动态规划表优化计算效率，避免浪费。
另外穷举也要求有一个方程来进行穷举，本质上是在于写出这个方程进行穷举的过程
PS: 下文中的代码可以在这个 github 项目找到源码以及相关的内容，欢迎关注提意见 star，谢谢！
斐波那契数列
结题方案有两种思路，一个是备忘录 memorandum 记录每次算过的值，从上往下，又称自顶向下。以及自底向上的 dp^1数组解法。
自顶向下
graph TD;
root(fib__5)-->|拆分为两个数相加的方程| fib__4
root(fib__5)-->|拆分为两个数相加的方程| fib__3
fib__4 --> memorandum__3
memorandum__3 -->|备忘录记录着fib__3的计算结果| fib__3
fib__4 --> fib__2
fib__3 --> memorandum__2
memorandum__2--> |备忘录记录着fib__2的计算结果|fib__2
fib__3 --> fib__1
title[自顶向下解法]
体现在代码的话是
package dynamic.programming;
import java.util.Arrays;
/**
* Fibonacci 斐波那契数列问题$
* <p>
* 创建时间： 2021/7/25 20:46
* 博客地址： <a href="https://tyrantqiao.com">详情戳我(╯‵□′)╯︵┻━┻)</a>
* <p>
* 问题：斐波那契数列黄金分割数列，1，1，2，3，5 之后的数是由前两数的累加而成
*
* @author tyrantqiao
* @version 1.0
**/
public class Fibonacci {
/**
* 暴力穷举
* <p>
* 问题： 比如说3，会在fib(5)计算一次，然后又在fib(4)中又算了一次，就造成了浪费
*
* @param whichNumber 第几位数
* @return 第几位数的值是啥
*/
public int fib(int whichNumber) {
if (whichNumber == 1 || whichNumber == 2) {
return 1;
}
return fib(whichNumber - 1) + fib(whichNumber - 2);
}
/**
* fib 备忘录版本，记录算过的值
*
* @param whichNumber 哪个数字
* @return 数字对应的值
*/
public int fibMemorandum(int whichNumber) {
if (whichNumber == 1) {
return 1;
}
int[] memorandumArray = new int[whichNumber + 1];
Arrays.fill(memorandumArray, 0);
return memorandumCalculate(memorandumArray, whichNumber);
}
/**
* 计算
* <p>
* 其实就是拿个数组记录下，也没有什么很突出的地方，这里数组记下，偷懒没有按照0开始操作的，所以数组记得多加一位定义
*
* @param memorandumArray 备忘录数组
* @param whichNumber 第几位数
* @return 返回结果
*/
private int memorandumCalculate(int[] memorandumArray, int whichNumber) {
if (whichNumber == 1 || whichNumber == 2) {
return 1;
}
if (memorandumArray[whichNumber] != 0) {
return memorandumArray[whichNumber];
}
return memorandumArray[whichNumber] =
memorandumCalculate(memorandumArray, whichNumber - 1)
+ memorandumCalculate(memorandumArray, whichNumber - 2);
}
public static void main(String[] args) {
System.out.println(new Fibonacci().fib(5));
System.out.println(new Fibonacci().fibMemorandum(5));
}
}
自底向上
与自顶向下一样都是用了数组记录已经算过的值，区别就在于计算的顺序变为了，从 f(1)+f(2) 、f(2)+f(3)的顺序开始，只是顺序不一样
/**
* 自底向上，其实跟上面自顶向下步骤是一样的，只是这边是从底部开始算，其实效率上都一样。
*
* @param whichNumber 第几位数
* @return 第几位数的数值是什么
*/
private int fibonacciFromBottom(int whichNumber) {
if (whichNumber < 1) {
return 0;
}
if (whichNumber == 1 || whichNumber == 2) {
return 1;
}
int[] dpArray = new int[whichNumber + 1];
dpArray[1] = dpArray[2] = 1;
for (int currentIndex = 3; currentIndex <= whichNumber; currentIndex++) {
dpArray[currentIndex] = dpArray[currentIndex - 1] + dpArray[currentIndex - 2];
}
return dpArray[whichNumber];
}
由上面的程序可以推导出这样的状态转移方程式
$$
f(n)=
\begin{cases}
1,& \text{n=1,2} \[5ex]
f(n-1)+f(n-2) & \text{n>2}
\end{cases}
$$
解开动态规划的核心在于找到这个方程，此外像本题中其实每轮计算都只需要两个状态 f(n-1)和 f(n-2)，我们只需要记录两个即可，不需要把整个斐波那契的计算过程记下来，空间密度由 n 降至了 2
/**
* 斐波那契压缩版，只记录fib(n-1)和fib(n-2)的状态
*
* @param whichNumber 第几位数
* @return 第几位数的值是什么
*/
private int fibonacciCompression(int whichNumber) {
if (whichNumber < 1) {
return 0;
}
if (whichNumber == 1 || whichNumber == 2) {
return 1;
}
int prev = 1, curr = 1;
int result = 0;
for (int currentIndex = 3; currentIndex <= whichNumber; currentIndex++) {
result = prev + curr;
prev = curr;
curr = result;
}
return result;
}
爬楼梯找硬币
本质和之前的斐波那契一样，重点是找到状态转移方程。
比如说题目：现在有十一块钱/十一层楼，但你只有1块钱or2块钱/每次走一层or两层楼梯的选择法，怎么样才可以最快到达楼层。
确定基本状态base case
找到常量的那个状态，我们可以很轻松地得知当楼层为0时，那么就不需要走了，楼层为1，那就只能选1，如果说楼层减成了负数，那也不需要再走下去了，直接返回-1代表失败即可。
$$
f(n)=
\begin{cases}
-1,& \text{n<0} \[5ex]
0 & \text{n==0} \[5ex]
1 & \text{n==1}
\end{cases}
$$
确定状态
找到状态转移方程中会不断变化的结果值，这样子才能向我们的base case方程去接近，当楼梯只有1层，那就只能选1，由此也可以看出我们的状态、变量也就是楼层/硬币
找到让状态变动的行为
如何让状态趋向base case，比如自顶向下那就要有减的过程，自底向上就要有加的过程。楼梯/硬币中我们每次有1/2的选择方式，选了1就相当于走了一层楼梯，加了一块钱，那我们的目标金额/楼层也就相应地减1，这样子就能够趋向我们的base case
明确dp函数怎么写
函数的参数变量一般是状态转移方程里面的状态变量值，对应着要到达的阶梯/硬币.
函数的返回值就是题目要求的东西，比如说最小达成目标的计算方式.
$$
f(n)=
\begin{cases}
0, & \text{n=0} \[5ex]
-1 & \text{n<0} \[5ex]
Math.min(dp(n-stair)+1|stair \in stairs), & \text{n>0}
\end{cases}
$$
代码实现
体现在代码的话如下
package dynamic.programming;
import java.util.Arrays;
import java.util.List;
/**
* 找到小费的最优组成形式$
* <p>
* 创建时间： 2021/7/26 6:35
* 博客地址： <a href="https://tyrantqiao.com">详情戳我(╯‵□′)╯︵┻━┻)</a>
*
* @author tyrantqiao
* @version 1.0
**/
public class CoinTip {
/**
* 暴力解法，本质在于不断求解子方程，并利用当等于0时，返回1，假如扣成负数，那就返回-1
*
* @param canUseCoinList 可以使用的硬币列表
* @param needToCombineTip 需要凑成的小费
* @return 最小数量是什么
*/
public int findMinCoinTipCombination(List<Integer> canUseCoinList, int needToCombineTip) {
if (needToCombineTip == 0) {
return 0;
}
if (needToCombineTip < 0) {
return -1;
}
int result = Integer.MAX_VALUE;
for (int eachCombinationCoin : canUseCoinList) {
int eachResult = findMinCoinTipCombination(canUseCoinList, needToCombineTip - eachCombinationCoin);
if (eachResult == -1) {
continue;
}
result = Math.min(result, 1 + eachResult);
}
return result == Integer.MAX_VALUE ? -1 : result;
}
/**
* 备忘录方法，本质在于不断求解子方程，并利用当等于0时，返回1，假如扣成负数，那就返回-1
*
* @param minCoinTipCombinationArray 每次计算的最小结果集
* @param canUseCoinList 可以使用的硬币列表
* @param needToCombineTip 需要凑成的小费
* @return 最小数量是什么
*/
public int findMinCoinTipCombinationMemorandum(int[] minCoinTipCombinationArray, List<Integer> canUseCoinList, int needToCombineTip) {
if (needToCombineTip == 0) {
return 0;
}
if (needToCombineTip < 0) {
return -1;
}
if (minCoinTipCombinationArray[needToCombineTip] != 0) {
return minCoinTipCombinationArray[needToCombineTip];
}
int result = Integer.MAX_VALUE;
for (int eachCombinationCoin : canUseCoinList) {
int eachResult = findMinCoinTipCombinationMemorandum(minCoinTipCombinationArray, canUseCoinList, needToCombineTip - eachCombinationCoin);
if (eachResult == -1) {
continue;
}
result = Math.min(result, 1 + eachResult);
}
return minCoinTipCombinationArray[needToCombineTip] = result == Integer.MAX_VALUE ? -1 : result;
}
public static void main(String[] args) {
List<Integer> canUseCoinList = Arrays.asList(1, 2, 5, 10);
int needToCombineTip = 22;
int[] minCoinTipCombinationArray = new int[needToCombineTip + 1];
Arrays.fill(minCoinTipCombinationArray, 0);
System.out.println(new CoinTip().findMinCoinTipCombination(canUseCoinList, needToCombineTip));
System.out.println(new CoinTip().findMinCoinTipCombinationMemorandum(minCoinTipCombinationArray, canUseCoinList, needToCombineTip));
}
}
package dynamic.programming;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
/**
* Stair combination$
* <p>
* 创建时间： 2021/7/26 22:27
* 博客地址： <a href="https://tyrantqiao.com">详情戳我(╯‵□′)╯︵┻━┻)</a>
*
* @author tyrantqiao
* @version 1.0
**/
public class StairCombination {
/**
* 阶梯组合
*
* @param allCombinationSize 一共有多少组合
* @param canUseStairList 可以使用的阶梯列表
* @param needToReachStair 需要到达的阶梯
* @return 阶梯组合
*/
public int findMinStairCombination(AtomicInteger allCombinationSize, List<Integer> canUseStairList, int needToReachStair) {
if (needToReachStair == 0) {
allCombinationSize.incrementAndGet();
return 0;
}
if (needToReachStair < 0) {
return -1;
}
int result = Integer.MAX_VALUE;
for (int canUseStair : canUseStairList) {
int eachResult = findMinStairCombination(allCombinationSize, canUseStairList, needToReachStair - canUseStair);
if (eachResult == -1) {
continue;
}
result = Math.min(result, eachResult + 1);
}
return result == Integer.MAX_VALUE ? -1 : result;
}
public int findMinStairCombinationMemorandum(int[] minCombinationMemorandum, List<Integer> canUseStairList, int needToReachStair) {
if (needToReachStair == 0) {
return 0;
}
if (needToReachStair < 0) {
return -1;
}
if (minCombinationMemorandum[needToReachStair] != 0) {
return minCombinationMemorandum[needToReachStair];
}
int result = Integer.MAX_VALUE;
for (int canUseStair : canUseStairList) {
int eachResult = findMinStairCombinationMemorandum(minCombinationMemorandum, canUseStairList, needToReachStair - canUseStair);
if (eachResult == -1) {
continue;
}
result = Math.min(result, eachResult + 1);
}
minCombinationMemorandum[needToReachStair] = result == Integer.MAX_VALUE ? -1 : result;
return minCombinationMemorandum[needToReachStair];
}
public static void main(String[] args) {
AtomicInteger allCombinationSize = new AtomicInteger(0);
int needToReachStair = 9;
System.out.println(new StairCombination().findMinStairCombination(allCombinationSize, Arrays.asList(1, 2), needToReachStair));
System.out.println("all: " + allCombinationSize);
int[] memorandumCombination = new int[needToReachStair + 1];
System.out.println(new StairCombination().findMinStairCombinationMemorandum(memorandumCombination, Arrays.asList(1, 2), needToReachStair));
}
}
