动态规划是运筹学的一个分支，是解决决策过程最优化的过程。20世纪50年代初，美国数学家R.Bellman等人在研究多阶段决策过程的最优化时，提出了著名的最优化原理，从而创立了动态规划。
在多阶段决策问题中，每个阶段做出的决策一般与时间有关，决策取决于当前状态(每个子问题都有一个状态)，然后导致状态转换(状态迭代)。一个决策序列是在变化的状态中产生的，因此具有“动态”的含义，这种求解多阶段决策优化的过程称为动态规划法。
当一个复杂的问题被分解时，会发现大量重复的问题。显然，没有必要对每个子问题做重复计算。可以保存子问题的结果(状态)，需要时直接取出存储的结果。达到以空间换时间的效果。
与贪婪方法类似，动态规划也是一种多阶段问题处理方法，适用于具有阶段单调性且满足最优子结构(一个优化策略的子策略总是最优的，或者问题的最优解包含其子问题的最优解)且无后效(前一阶段做出的选择不应对后一阶段的最优选择产生副作用或影响，或者前一阶段做出的选择在后一阶段做出最优选择时不能进行追溯性修改或调整)的应用问题。如果子问题重叠很多，可以选择动态规划，通过状态记忆消除计算冗余(计算时存储子问题的状态，用存储的状态进行计算)。
动态规划是基于搜索优化、分治和贪婪方法的独特集成。它与其他算法的区别如下：
动态规划与其他算法在确定各阶段最优状态时的区别；
动态适用场景：
以下三类问题一般适用于动态规划：
动态规划分类和一般适用场景：
坐标动态规划
顺序动态规划
分区动态规划
区间动态规划
背包动态规划
最长序列动态规划
游戏动态编程
综合动态规划
爆裂气球
最长回文子序列
背包
买卖股票的最佳时机
解码方式
最大平方
剩余价值背包
独特的路径
跳跃游戏
解码方式
油漆房
流浪剑客斯文
k线和
最长增长子序列
问题：硬币有三种，面值分别是X，Y，z，现在给一个量C，需要多少硬币才能凑成量C？
递归解决方案：
假设三枚硬币的面值分别为2、5、7，金额为27。
逆向思维(自上而下):
演示代码：
public class Main { public static void Main(String[]args){ int[]arr={ 1，3，5 }；//这里的量{2.5.7}不是用来聚集27的，因为递归时堆栈溢出int c=16int num=func (arr，c)；system . out . println(\’ num:\’ num \’)；system . out . println(\’ number:\’ number \’)；}静态int数=0；//记录递归次数私有静态int func (int [] arr，int c){ if(c==0){ return 0；}数字；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])；返回Math.min (Math.min (n1，n2)，n3)；} } } }/* num:4 number:502 */递归求解时，涉及大量重复的子问题。
递归带有一个数组来存储子问题的结果：
导入Java。util。数组；public class Main { public static void Main(String[]args){ int[]arr={ 2，5，7 }；int c=27int[]DP=new int[c 1]；//记录组成价值我所需要的最少的硬币的数量Arrays.fill(dp，-1)；int num=func(arr，c，DP)；系统。出去。println(\’ num:\’ num \’)；系统。出去。println(\’ number:\’ number \’)；}/*阵列数组放的是硬币，c是指定的价值，返回价值c最少需要的硬币的数量*/静态（同Internationalorganizations）国际组织数=0;//计算递归的次数private static int func(int[] arr，int c，int[] dp) { if(dp[c]！=-1){ return DP[c]；}数字；if(c==0){ DP[c]=0；返回0;} if(c==1 | | c==3 | | c==5){ DP[c]=1；返回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]；} }}动态规划求解：
不但将中间结果（状态)保存下来，同时改变计算顺序，使用状态转移方程。
顺向思维（自下而上):
为简单起见，假设三种硬币的面值是1,3,5,金额是11。
动态规划解决问题，关键有3点：1 \”状态\” dp[sum]:组成金额总和所需要的最少的硬币的数量2状态转移方程（对于迭代关系，但更复杂，需要考虑一个或多个状态)3 计算顺序，直接影响实现的难易程度五[j]:表示第j种硬币的面值，其值域是{1，3，5}dp[sum]:组成金额总和所需要的最少的硬币的数量— 状态DP[0]=0dp[1]=1 DP[1-1]=1 DP[0]=1dp[2]=1 DP[2-1]=1 DP[1]=2dp[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]，1dp[v-5]} DP[sum]=min { 1dp[sum-v[j]]}，sum=v[j]，sum表示要组成的多管，v[j]表示第j个硬币的面额代码演示：
导入Java。util。数组；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。长度；j ) {数字；//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]]；} } }系统。出去。println(数组。tostring(DP))；//打印数据处理数组（即：组成价格C前所有整数价格的硬币个数)系统。出去。println(\’ num:\’ DP[c])；系统。出去。println(\’ number:\’ number \’)；}}C代码演示：
# include iostream #使用命名空间std定义MAXINT 32767；main(){ int sum，kindsCout \’货币总额和硬币种类：\’；cinsumkinds//int * val=new int[kinds]；int * DP=new int[sum 1]；Cout \’输入从小到大各种硬币的面额：\’；int i，j；for(j=0；jkinds辛瓦尔[j]；//val[j]表示j硬币的面值for(I=1；I=总和；I)DP[I]=MAXINT；//dp[i]表示和为I时的最小硬币数，初始化为MAXINT DP[0]=0；//边界条件为(I=1；I=总和；I) //前一阶段的最优值与穷举增量相结合，形成(j=0；jkindsJ ){ //穷举面值if(val[j]=I DP[I-val[j]]1 DP[I])//动态决策DP[I]=DP[I-val[j]]1；} cout \’所需硬币的最小数量：\’ DP[sum]endl；cout \’ moneyminimum coin\’ endl；for(I=0；I=总和；I)cout I”DP[I]endl；getchar()；getchar()；}/*总金额及硬币种类种类：27 3从小到大输入各类硬币的面值：2 5 7所需最少硬币数：5钱最少硬币数0 01 327672 13 32725 16 37 18 49 210 211 312 213 414 215 316 317 318 419 320 421 322 423 423。
动态规划通常可分为四个步骤：
具体可参考以上硬币收藏(硬币区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动态编程的计算顺序计算顺序决定了状态转换的方向，直接影响代码的复杂度。通常是自底向上递归。
递归的枚举和状态转移(是单向的，但不是单变量递归，而是根据转移方程结合所需子问题的状态进行的递归):
演示代码：
/*包随便；//不要放置包名！*/导入Java。util。*;导入Java。郎。*;导入Java。io。*;/*只有当类是公共的时，类的名称才必须是主要的.*/class Ideone { public static int coin change(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]=整数MAX _ value for(j=0；jn；j){ if(i=a[j] f[i-a[j]]！=整数. MAX_VALUE){ f[i]=Math.min(f[i]，f[I-a[j]]1)；} } } if(f[m]==整数. MAX _ VALUE)f[m]=-1；return f[m]；}公共静态void main (String[] args)抛出java.lang.Exception { int[] a={2，5，7 }；int n=coinChange(a，27)；系统。出去。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-毕丽-hx
https://web.ntnu.edu.tw/~algo/DynamicProgramming.html
https://www.geeksforgeeks.org/dynamic-programming/
https://www.topcoder.com/thrive/articles/Dynamic编程：从新手到高级
沈军沈凌翔《计算思维之快乐编程》
-结束-