动态规划是常用的算法之一，这里简单记录一下几个经典题目，ps:以上题目都是出自力扣，这里单纯做个总结，侵权必删！
1，斐波那锲数列问题
斐波那锲数列1,1,2,3,5,8,13，。。。
给N输出数列第N个数
/**
* 动态规划解决斐波那锲数列问题
* 规律：f(n) = f(n-1) + f(n-2);
*/
public static int testFeibo(int n){
if(n <= 2){
return 1;
}
int[] dp = new int[n];
dp[0] = dp[1] = 1;
for(int i = 2;i < n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
2,上台阶问题
上楼梯问题，一次只能上1 or 2；一个n阶的楼梯，有多少走法？
/**
* 在所有跳法中，最后一步只有两种情况： 跳上 1级或 2级台阶
* 定义f(n)为第n阶台阶走法，因为最后一步要么1阶（走法f(n-1)），要么2阶(走法f（n-2）)。所以f(n) = f(n-1) + f(n-2)
* @param n
* @return
*/
private static int testStairs(int n){
if(n <= 1){
return 1;
}else{
int[] dp = new int[n+1];
dp[0] = dp[1] = 1;
for(int i = 2;i < n+1;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
3,最大连续子串问题
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。例如
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
/**
* 最大连续子串问题
* 定义dp[i] 是以arr[i]为尾数的最大值
* 如果dp[i-1]>0 ,dp[i] = dp[i-1] + arr[i]
* 否则 dp[i] = arr[i];
* 给定数组arr
* @return
*/
public static int testMaxSubArr(int[] arr){
int [] dp = new int[arr.length];
dp[0] = arr[0];
int max = dp[0];
for(int i = 1;i < arr.length;i++){
if(dp[i-1] > 0){
dp[i] = dp[i-1] + arr[i];
}else{
dp[i] = dp[i-1];
}
max = max > dp[i] ? max : dp[i];
}
return max;
}
4，股票最大利润问题
假设把某股票的价格按照时间先后顺序存储在数组中，求买卖该股票一次可能获得的最大利润是多少？
例如：
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 ；（）利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
/**
* 股票最大利润问题：
* 定义dp[i-1] 为第i天最大利润；
* dp[0] = 0;第1天没有利润
* 假设股价最低是min
* 如果prices[i] - min > dp[i-1];dp[i] = prices[i] - min;
* 否则 dp[i] = dp[i-1];
* @param prices
* @return
*/
public static int testMaxProfit(int[] prices) {
int dp[] = new int[prices.length];
dp[0] = 0;
int min = prices[0];
for(int i = 1; i < prices.length;i++){
min = min < prices[i] ? min : prices[i];
if(prices[i] - min > dp[i-1]){
dp[i] = prices[i] - min;
}else{
dp[i] = dp[i-1];
}
}
return dp[dp.length-1];
}
5，礼物的最大价值问题
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
/**
* 二维数组最大路径和：
* 只能向右或者下移动一步，到达i,j的最大值
* 假设dp[i][j] 记录了到grid[i][j]的最大值
* 如果i=j=0;则dp[i][j] = grid[i][j]；
* 如果i=0;j>0 ,则dp[i][j] = dp[i][j-1] + grid[i][j];
* 如果i>0;j=0,则dp[i][j] = dp[i-1][j] + grid[i][j];
* 其他则dp[i][j] = max(dp[i][j-1],dp[i-1][j])+grid[i][j];
* @param grid
* @return
*/
public static int testMaxValue(int[][] grid) {
int x = grid.length;
int y = grid[0].length;
int[][] dp = new int[x][y];
for(int i = 0; i < x;i++){
for(int j = 0;j < y;j++){
if(i == 0 && j==0){
dp[i][j] = grid[i][j];
}else if(i == 0 && j>0){
dp[i][j] = dp[i][j-1] + grid[i][j];
}else if(i > 0 && j==0){
dp[i][j] = dp[i-1][j] + grid[i][j];
}else{
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
}
}
}
return dp[x-1][y-1];
}
总结：动态规划问题的核心在于定于dp函数，找个i和i-1之间的关系，可以有限降低算法的复杂度。
