动态规划（英语：Dynamic programming，简称 DP）
是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。斐波那契数列 0,1,1,2,3,5,8,13,…有着一个相当简单的描述方式，它的每个数字都与前两个紧邻的数字相关。如果 F(n) 是第 n 个数字，那么我们会有 F(n) = F(n-1) + F(n-2)。这个在数学上称作递归方程或者递推关系。为了计算后面的项，它需要前面项的计算结果作为输入。
解决方案
自上而下：
你从最顶端开始不断地分解问题，直到你看到问题已经分解到最小并已得到解决，之后只用返回保存的答案即可。这叫做记忆存储（Memoization）。
自下而上：
你可以直接开始解决较小的子问题，从而获得最好的解决方案。在此过程中，你需要保证在解决问题之前先解决子问题。这可以称为表格填充算法（Tabulation，table-filling algorithm**）。
至于迭代和递归与这两种方法的关系，自下而上用到了迭代技术，而自上而下则用到了递归技术。
动态规划、分治法、贪心算法异同点
相同点：
动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。
不同点：
-
分治法
分治法中的各个子问题是独立的，利用子问题的解，合并成该问题的解。
-
贪心算法
只有同一个问题，依赖于当前已经做出的所有选择。
自顶向下处理，每一步，根据策略得到一个当前最优解。传递到下一步，从而保证每一步都是选择当前最优的。
-
动态规划
动态规划中的各个子问题是不独立的，动态规划任何一个i+1阶段都仅仅依赖 i 阶段的处理，而与i之前的选择无关。
自底向上处理，每一步，根据策略得到一个更小规模的问题。最后解决最小规模的问题，得到整个问题最优解。
各题题解：
// ###### [爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/) ★
public int climbStairs(int n) {
//思路：用动态规划思想，要爬到n阶，可以通过最后爬一步和两步2中爬法到，到n阶的方法等于到n-1阶方法加上n-2阶方法，即f(n)=f(n-1)+f(n-2)，这个f(n)方法就用递归实现
//此外，f(n)=f(n-1)+f(n-2)，从n为3开始，该函数计算得出的是一个斐波那契数列，当前数为前两个数之和，所以有两种解法
if (n < 3) {
return n;
}
int a = 1;
int b = 2;
int cur = 0;
for (int i=3;i<=n;i++) {
cur = a + b;
a = b;
b = cur;
}
return cur;
}
// ###### [最大子数组和](https://leetcode.cn/problems/maximum-subarray/)★
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i=1;i<nums.length;i++) {
//如果i前一个数的子数组和小于0，就不要加上前面的累赘了，否则就加上
dp[i] = nums[i] + Math.max(dp[i-1], 0);
//遍历的同时获取dp数组中的最大值
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}
// ###### [零钱兑换](https://leetcode.cn/problems/coin-change/)
/**
* 示例： 1 2 3 面值， 要凑齐5元
* 凑钱数的最小硬币数 = Min(1个1元硬币 + 凑齐4元所需硬币数, 1个2元硬币 + 凑齐3元所需硬币数, 1个3元硬币 + 凑齐2元所需硬币数)
* 思路：dp[i]表示对应价格i所需最小硬币数，coins表示硬币面值
* 则 dp[i] = min(1+dp[p-coins[j]])
*/
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
// ###### [打家劫舍](https://leetcode.cn/problems/house-robber/)
/**
* 要解前n间房能偷的最大金额，那就尝试先从前1、2、3间能偷的最大金额找规律
Sn表示前n间房能偷的最大金额 Hn表示第n间房的金额
示例： [1,2,3,1]
前1间房能偷的最大金额 S1 = H1 = 1
前2间房能偷的最大金额 S2 = max(S1,H1) = 2
从第三间房开始，就有2种偷法了，就是偷第n间房和不偷第n间房
偷第n间房，那就不能偷n-1间房，能偷n-2间房 那么最大金额不一样的取决于最近这三间房怎么偷，因为前Sn-2都一样
前3间房能偷的最大金额 S3 = max(S2, H3+S1) = 4
前n间房能偷的最大金额 Sn = max(Sn-1, Hn+Sn-2)
*/
public int rob(int[] nums) {
int length = nums.length;
if(length <= 1) {
return nums[0];
}
int[] dp = new int[length]; //dp[i]表示前i间房能偷的最大金额
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i=2;i<length;i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[length-1]; //这里需要得到前n间房的最大值，所以是返回dp[length-1]
}
