image.png
前言
动态规划不管是在笔试还是面试还是日常开发中也是比较常见的一种算法。今天主要简单的介绍一些动态规划的一些知识。
都是一些日常的积累，有问题可以指出来哦
基本概念
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
思想
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
使用条件
- 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
- 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
- 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
求解过程
- 将原问题分解为子问题
把原来的问题分解为若干的子问题，子问题和原问题是相似的，可能就是规模变小了。- 确定状态
子问题相关的一组值，将作为状态，实际上状态就是子问题的解。- 确定初始状态和边界值
- 确定状态转移方程
根据已知的状态得到未知的后序状态，得到一组递推方程，就是状态转移方程。
举个例子
求最大连续子序列和问题。
给定一个数组[1 ，-5 ，2 ，4， -1， -5 ]；
求连续子序列和最大。
1、 分解问题
上述为6个数的数组求解最大连续子序列和，转化为将某个数作为子序列末尾求子序列最大和问题。
2、 确定状态
数组中i作为子序列尾部时最大的和作为状态。
3、 确定初始状态和边界
初始状态均为数组值
4、 状态转移方程
数组第i个作为子序列尾部，第i-1个子序列位数的状态为a，如果i加上a的状态大于i本身的状态，i的状态需要加上i-1的状态，反之状态不变。
得到状态方程：
dp[i]=max{dp[i-1]+array[i],array[i]};
代码
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
int n=input.nextInt();
int []array=new int[n];
for (int i = 0; i <n ; i++) {
array[i]=input.nextInt();
}
int []dp=new int[n];
dp[0]=array[0];
for (int i = 1; i <n ; i++) {
dp[i]=Math.max(array[i],dp[i-1]+array[i]);
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (max < dp[i]) {
max = dp[i];
}
}
System.out.println(max);
}
