动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。
在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态（各子问题都有一个状态），又随即引起状态的转移（状态迭代），一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。
当一个复杂问题分解时，发现有大量重复的大问题，显然没必要对每个子问题做重复计算，可以将子问题的结果（状态）存起来，在需要时直接取出这个存储的结果。达到以空间换时间的效果。
与贪心方法类似，动态规划也是一种多阶段问题处理方法，适用于具有阶段单调性特征并满足最优子结构（一个最优化策略的子策略总是最优的，或者说一个问题的最优解中包含了其子问题的最优解）和无后效性特征（以前阶段已做的选择不应该对后面阶段的最优选择带来副作用或影响，或后面阶段进行最优选择时不能再对以前阶段已做的选择进行回溯修改或调整）的应用问题的最优值求解。如果子问题有大量重叠，便可以选择动态规划，通过状态记忆来消除计算冗余（边计算边存储子问题的状态，并利用存储的状态做计算）。
动态规划是一种基于搜索优化、分治、贪心方法的仅此集成，其与其它算法的区别如下：
动态规划在每阶段确定最优状态时与其它算法的区别：
动态规划的适用场景：
如下三类问题一般适用动态规划：
动态规划分类及通常适用场景：
坐标型动态规划
序列型动态规划
划分型动态规划
区间型动态规划
背包型动态规划
最长序列型动态规划
博弈型动态规划
综合型动态规划
Burst Balloons
Longest Palindromic Subsequence
Backpack
Best Time To Buy And Sell Stock
Decode Ways
Maximal Square
Surplus Value Backpack
Unique Paths
Jump Game
Decode Ways
Paint House
Rogue Knight Sven
K-Sum
Longest Increasing Subsequence
问题：有面值x，y，z分的三种硬币，现在给出一个金额C，问组成金额C最少需要几枚硬币?
递归求解：
假设三种硬币的面值是2，5，7，金额是27。
逆向思维（top-down）：
demo code：
public class Main {
public static void main(String[] args) {
int[] arr = {1, 3, 5}; // 这里没有使用金额{2.5.7}凑27，因为递归时会栈溢出
int c = 16;
int num = func (arr, c);
System.out.println ("num：" + num);
System.out.println ("number: " + number);
}
static int number = 0;//记录递归的次数
private static int func(int[] arr, int c) {
if (c == 0) {
return 0;
}
number++;
if (c == arr[0] || c == arr[1] || c == arr[2]) {
return 1;
} else {
if (c < arr[1]) {
return 1 + func (arr, c - arr[0]);
} else if (c < arr[2]) {
int n1 = 1 + func (arr, c - arr[0]);
int n2 = 1 + func (arr, c - arr[1]);
return Math.min (n1, n2);
} else {
int n1 = 1 + func (arr, c - arr[0]);
int n2 = 1 + func (arr, c - arr[1]);
int n3 = 1 + func (arr, c - arr[2]);
return Math.min (Math.min (n1, n2), n3);
}
}
}
}
/*
num：4
number: 502
*/递归求解时，涉及到大量重复子问题的重复计算。
递归附带一个数组存储子问题结果：
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {2,5,7};
int c = 27;
int[] dp = new int[c+1];//记录组成价值i所需要的最少的硬币的数量
Arrays.fill(dp, -1);
int num = func(arr,c,dp);
System.out.println ("num：" + num);
System.out.println ("number: " + number);
}
/*arr数组放的是硬币，c是指定的价值，返回价值c最少需要的硬币的数量
*/
static int number = 0; //计算递归的次数
private static int func(int[] arr, int c,int[] dp) {
if(dp[c] != -1){
return dp[c];
}
number++;
if(c == 0){
dp[c] = 0;
return 0;
}
if(c == 1 || c == 3 || c == 5){
dp[c] = 1;
return 1;
}else {
if(c < arr[1]){
dp[c] = 1 + func (arr,c-arr[0],dp);
}else if(c < arr[2]){
int n1 = 1 + func (arr,c-arr[0],dp);
int n2 = 1 + func (arr,c-arr[1],dp);
dp[c] = Math.min (n1,n2);
}else{
int n1 = 1 + func (arr,c-arr[0],dp);
int n2 = 1 + func (arr,c-arr[1],dp);
int n3 = 1 + func (arr,c-arr[2],dp);
dp[c] = Math.min (Math.min (n1,n2),n3);
}
return dp[c];
}
}
}动态规划求解：
不但将中间结果（状态）保存下来，同时改变计算顺序，使用状态转移方程。
顺向思维（bottom-up）：
为简单起见，假设三种硬币的面值是1，3，5，金额是11。
动态规划解决问题，关键有3点：
1 “状态” dp[sum] : 组成金额sum所需要的最少的硬币的数量
2 状态转移方程（对于迭代关系，但更复杂，需要考虑一个或多个状态）
3 计算顺序，直接影响实现的难易程度。
v[j]：表示第j种硬币的面值，其值域是{1,3,5}
dp[sum] : 组成金额sum所需要的最少的硬币的数量 —> 状态
dp[0] = 0
dp[1] = 1 + dp[1-1] = 1 + dp[0] = 1
dp[2] = 1 + dp[2-1] = 1 + dp[1] = 2
dp[3]:
1 + dp[3-1] = 1 + 2 = 3
1 + dp[3-3] = 1 + 0 = 1
.......
dp[sum] = min{1+dp[sum-1], 1+dp[sum-3], 1+dp[v-5]}
dp[sum] = min{1 + dp[sum-v[j]]}, sum >= v[j], sum表示要组成的多管，v[j]表示第j个硬币的面额code demo：
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] v = {2, 5, 7};
int c = 27;
int number = 0;
int[] dp = new int[c + 1];
for (int i = 1; i <= c; i++) {
dp[i] = 99999;
for (int j = 0; j < v.length; j++) {
number++;
// i 1 + dp[1-1] 1 + dp[i-3] 1 + dp[i-5]
if (i >= v[j] && 1 + dp[i - v[j]] < dp[i]) {
dp[i] = 1 + dp[i - v[j]];
}
}
}
System.out.println (Arrays.toString (dp));//打印dp数组（即：组成价格C前所有整数价格的硬币个数）
System.out.println ("num：" + dp[c]);
System.out.println ("number：" + number);
}
}C++ code demo：
#include <iostream>
#define MAXINT 32767
using namespace std;
main()
{
int sum,kinds;
cout<<"总钱数sum和硬币种类kinds：";
cin>>sum>>kinds; //
int *val = new int[kinds];
int *dp = new int[sum+1];
cout<<"从小到大输入各类硬币面值：";
int i,j;
for(j=0;j<kinds;j++)
cin>>val[j]; // val[j]表示第j种硬币的面值
for(i=1;i<=sum;i++)
dp[i] = MAXINT; // dp[i]表示sum为i时的最小硬币数目，初始化为MAXINT
dp[0] = 0; // 边界条件
for(i=1;i<=sum;i++) // 前面阶段最优值与可穷举增量组合以构成当前最优解
for(j=0;j<kinds;j++){ // 穷举面值
if(val[j]<=i && dp[i-val[j]]+1 < dp[i]) // 动态决策
dp[i]=dp[i-val[j]]+1;
}
cout<<"需要的最少硬币个数："<<dp[sum]<<endl;
cout<<"钱数↓ 最少硬币个数↓"<<endl;
for(i=0;i<=sum;i++)
cout<< i <<" "<<dp[i]<<endl;
getchar();
getchar();
}
/*
总钱数sum和硬币种类kinds：27 3
从小到大输入各类硬币面值：2 5 7
需要的最少硬币个数：5
钱数↓ 最少硬币个数↓
0 0
1 32767
2 1
3 32767
4 2
5 1
6 3
7 1
8 4
9 2
10 2
11 3
12 2
13 4
14 2
15 3
16 3
17 3
18 4
19 3
20 4
21 3
22 4
23 4
24 4
25 5
26 4
27 5
*/由以上问题来总结一下动态规划的一般思路。
动态规划一般可以分为四个步骤考量：
如具体到以上硬币凑钱（硬币面积2，5，7，金额27）问题：
① 确定状态
最后一步（最优策略中使用的最后一枚硬币）
转化子问题（除掉最后一枚，前面的硬币数27-）
② 转移方程
f[x]=min{f[x-2],f[x-5],f[x-7]}
③ 初始条件和边界情况
f[0]=0，如果不能拼出Y，f[Y]=正无穷
④ 计算顺序
f[0],f[1],f[2],……
(要算一个新状态时，要用到的其它状态要先算出来，
等号左边是要算的，等号右边是要用的，要用的要先算出来)
1 确定状态
状态如何用数据表示，通常使用一个一维或二维数组，或使用几个变量（如斐波那契数列可以使用两个变量存储初始状态，然后迭代）。
2.1 从最后一步倒推：
1.2 原问题转化为子问题：
所有各阶段的子问题构成一个单调的阶段序列，合并解操作就是统一为“动态决策”。
除第一个阶段外，其他每阶段的最优选择（或决策）建立在前面阶段最优解的基础上，该决策细分为两个基本步骤：
① 找出与当前阶段决策有关系的前面阶段中的各种最优解（或与当前问题相关的各种子问题的解），并与本阶段各个增量值（这里是1，即增加一个硬币）进行组合，构成当前阶段的所有可能 / 候选状态。（这里有关系的是当前金额减去三种硬币面值的状态，枚举3次）
② 从当前所有可能 / 候选状态中选择一个最优状态（这里是求最少硬币数），其值就是当前阶段的最优解。显然，这个最优决策行为具有动态性。
2 确定各阶段的状态转移方程
状态转移方程无论是顺推还是倒推，其递推逻辑必须满足单调性。
3 确定状态的初始条件和边界条件
初始条件是状态转移的基准，边界条件包括转移的结束条件或计算范围。
4 动态规划的计算顺序
计算顺序决定状态转移的方向，直接影响代码的复杂度。通常是从底向上递推。
递推时的枚举及状态转移（是单向，但不是单变量递推，而是结合需要的子问题的状态按转移方程递推）：
demo code:
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static int coinChange(int[] a,int m){
int[] f = new int[m+1];
int n = a.length;
f[0] = 0;
int i,j;
for(i=1;i<=m;++i){
f[i] = Integer.MAX_VALUE;
for(j=0;j<n;++j){
if(i>=a[j] && f[i-a[j]] != Integer.MAX_VALUE){
f[i] = Math.min(f[i],f[i-a[j]]+1);
}
}
}
if(f[m] == Integer.MAX_VALUE)
f[m]=-1;
return f[m];
}
public static void main (String[] args) throws java.lang.Exception
{
int[] a = {2,5,7};
int n = coinChange(a,27);
System.out.println(n); // 5
}
}ref
https://blog.csdn.net/qq_44825669/article/details/96614037
https://www.bilibili.com/video/BV1gp4y1t7xe
https://www.jiuzhang.com/course/36/?utm_source=sc-bili-hx
https://web.ntnu.edu.tw/~algo/DynamicProgramming.html
https://www.geeksforgeeks.org/dynamic-programming/
https://www.topcoder.com/thrive/articles/Dynamic%20Programming:%20From%20Novice%20to%20Advanced
沈军 沈凌翔 《计算思维之快乐编程》
-End-