什么问题是动态规划问题？
动态规划问题的一般形式就是求最值；
求解动态规划的核心问题是穷举。
- 动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP
table」来优化穷举过程，避免不必要的计算。 而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。
动态规划三要素:
- 重叠子问题、 解决：备忘录 或者 DP table
- 最优子结构、 注意：必须子问题是独立的！
- 状态转移方程、
辅助你思考状态转移方程：
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
如何列出正确的状态转移方程？
根据下面案例进行解释：
根据案例： 凑零钱问题–>解决最优子结构
先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
// coins 中是可选硬币面值，amount 是目标金额
int coinChange(int[] coins, int amount);
比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
你认为计算机应该如何解决这个问题？显然，就是把所有可能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。
1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。
所以我们可以这样定义 dp 函数：dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。
实战一、斐波那契数列–>解决重叠子问题
分析：
base case：显然目标数值n<0 =1 =2 的时候的取值；
状态：–
选择： –
状态转移函数：当前数值为前两个数的和
package com.learn.science.algorithm.zhijian;
import io.swagger.models.auth.In;
import java.util.HashMap;
import java.util.Map;
/**
* @author kaka
* @date 2021/2/7
*/
public class DPZ101fib {
/**
剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：0 <= n <= 100
1 1 2 3 5 8 13 ...
*/
// 方法一：递归暴力请求，效率低下（原因：大量重复计算子问题）
public static int fib_dg(int n) {
if (n == 0 || n == 1) {
return n;
}
return fib_dg(n - 1) + fib_dg(n -2);
}
// 方法二：带有备忘录的求解
// 思想：将重复计算优化掉
// 使用备忘录，将结果子问题记录，解决问题先去查是否处理过子问题，如果处理过直接拿结果，如果没有在处理，处理完存入备忘录；
public static int fib_bwl(int n) {
if (n < 1) {
return 0;
}
// 备忘录全初始化为 0
Map<Integer, Integer> memo = new HashMap<>();
// 进行带备忘录的递归
return fib_bwl_dg(memo, n);
}
public static int fib_bwl_dg(Map<Integer, Integer> memo, int n) {
// base case
if (n == 1 || n == 2) {
return 1;
}
// 已经计算过
if (memo.get(n) != null) {
return memo.get(n);
}
// 没计算过计算
int result = fib_bwl_dg(memo, n - 1) + fib_bwl_dg(memo, n - 2);
// 存储备忘录
memo.put(n, result);
return memo.get(n);
}
// 方法三：dp数组的迭代解法
// 思想：有了上面的备忘录解法，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算
public static int fib_dp(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
// dp初始化
Map<Integer, Integer> dp = new HashMap<>();
// base case
dp.put(1, 1);
dp.put(2, 1);
for (int i = 3; i <= n; i ++) {
dp.put(i, dp.get(i - 1) + dp.get(i - 2));
}
return dp.get(n);
}
// 方法四：基于dp的状态压缩
// 因为此题不是最值问题，不需要记录全部状态，只需要记录前两个状态即可；所以可以将状态记录的DPtable压缩；
public static int fid_ztys(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int per1 = 1, per2 = 1; // 前面两个值，不需要全部的状态值，这个只需要记录两个状态值。
int sum = 0;
for (int i = 3; i <= n; i ++) {
sum = per1 + per2;
per1 = per2;
per2 = sum;
}
return sum;
}
public static int fib(int n) {
int a = 0, b = 1, sum;
for (int i = 0; i < n; i ++) {
// sum = a + b;
sum = (a + b)%1000000007;
a = b;
b = sum;
}
return a;
}
public static void main(String[] args) {
System.out.println(fid_ztys(10));
}
}
实战二、凑零钱问题–>解决最优子结构
二、凑零钱问题–>解决最优子结构
先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
// coins 中是可选硬币面值，amount 是目标金额
int coinChange(int[] coins, int amount);
比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
你认为计算机应该如何解决这个问题？显然，就是把所有可能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。
分析动态规划的条件：
base case：这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
状态： amount
选择： 硬币种类，目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
状态转移函数：动态规划又做自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。
所以我们可以这样定义 dp 函数：
dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。
package com.learn.science.algorithm.zhijian;
import io.swagger.models.auth.In;
import java.util.HashMap;
import java.util.Map;
/**
* @author kaka
* @date 2021/2/9
*/
public class DPcoinChange {
/**
先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再
给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
算法的函数签名如下：
// coins 中是可选硬币面值，amount 是目标金额
int coinChange(int[] coins, int amount);
比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
你认为计算机应该如何解决这个问题？显然，就是把所有可能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。
1，暴力递归
最优子结构，子问题必须互相独立；
原问题：要考总分最高分；
子问题：每一门课都考最高分，语文，数据，英语都考最高。 子问题不互相影响，考语文不会影响我数据和英语的分数；
原问题：给定金额找出用最少多少枚硬币；
子问题，米格
*/
/**
// coins 中是可选硬币面值：List[int]= 1 2 5 三种面值的硬币
// amount 是目标金额：int amount=11 总金额
// 伪码框架
int coinChange(int[] coins, int amount) {
// 定义凑出金额n，至少要dp(n)个硬币
def dn(n) {
// 做选择，选择需要硬币最少的那个结果
for (int coin : coins) {
res = min(res, 1 + dp(n - coin));
return res;
}
}
// 题目要求的最终结果是 dp(amount)
return dp(amout);
}
*/
/**
如何列出正确的状态转移方程？
1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。
// 所以我们可以这样定义 dp 函数：!!!!!!!!!!!! 最难的是找到状态转移函数
// dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。
*/
// 方法一：暴力递归
public static int coinChange_dg(int[] coins, int amount) {
// base case
if (amount < 0) {
return -1;
}
if (amount == 0) {
return 0;
}
// 状态：amount
// 选择：选择硬币，导致状态变化
int cnums = Integer.MAX_VALUE; // 求最小值，设置为无穷大
for (int coin : coins) {
// 子问题选择硬币
int subproblem = coinChange_dg(coins, amount - coin);
// 子问题无解跳过
if (subproblem == -1) {
continue;
}
// 有解看哪个小
cnums = Math.min(cnums, subproblem + 1);
}
if (cnums == Integer.MAX_VALUE) {
cnums = -1;
}
return cnums;
}
// 方法二：带有备忘录的求解
// 思想：将重复计算优化掉
// 使用备忘录，将结果子问题记录，解决问题先去查是否处理过子问题，如果处理过直接拿结果，如果没有在处理，处理完存入备忘录；
public static int coinChange_bwl(int[] coins, int amount) {
if (amount < 0) {
return -1;
}
if (amount == 0) {
return 0;
}
// 初始化备忘录 : key:状态金额，value:硬币数
Map<Integer, Integer> map = new HashMap<>();
// 找最小硬币数
return coinChange_bwl_dg(coins, amount, map);
}
public static int coinChange_bwl_dg(int[] coins, int amount, Map<Integer, Integer> map) {
// base case
if (amount < 0) {
return -1;
}
if (amount == 0) {
return 0;
}
// 备忘录查找
if (map.get(amount) != null) {
return map.get(amount);
}
int cnums = Integer.MAX_VALUE;
// 没有，进行选择计算
for (int coin : coins) {
// 子问题
int sub_num = coinChange_bwl_dg(coins, amount - coin, map);
// 无解
if (sub_num == -1) {
continue;
}
cnums = Math.min(cnums, sub_num + 1);
}
// 记录备忘录
map.put(amount, cnums == Integer.MAX_VALUE ? -1 : cnums);
return coinChange_bwl_dg(coins, amount, map);
}
// 方法三：dp数组的迭代解法
// 思想：有了上面的备忘录解法，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算
public static int coinChange_dp(int[] coins, int amount) {
if (amount < 0) {
return -1;
}
if (amount == 0) {
return 0;
}
// 定义dp数组
Map<Integer, Integer> map = new HashMap<>();
return coinChange_dp_dg(coins, amount, map);
}
public static int coinChange_dp_dg(int[] coins, int amount, Map<Integer, Integer> map) {
// base case
map.put(0, 0);
// 外层 for 循环在遍历所有状态的所有取值
for (int i = 1; i <= amount; i ++) {
// 内层 for 循环在求是所有选择的最小值
for (int coin : coins) {
// 子问题无解，跳过
if (i - coin < 0) {
continue;
}
// 子问题解
int sub_num = coinChange_dp_dg(coins, i - coin, map);
sub_num = map.get(i) == null ? sub_num + 1 : Math.min(map.get(i), sub_num + 1);
// 存储dp
map.put(i, sub_num);
}
}
return map.get(amount) == null ? -1 : map.get(amount);
}
public static void main(String[] args) {
System.out.println(coinChange_dg(new int[]{1,2,5}, 11));
System.out.println(coinChange_bwl(new int[]{1,2,5}, 11));
System.out.println(coinChange_dp(new int[]{1,2,5}, 11));
}
}
读书笔记，学习笔记。