动态规划在我眼里是很缥缈的，也是需要花很长时间去练习巩固的。其实在理解动态规划之前正确的顺序应该是先写递归，因为很多动态规划的转移方程都是通过递归加记忆法从而推导出公式，但是我随性，所以就不按套路出牌了。接下来就是简单介绍一下动态规划以及应用场景，最后把之前刷过的动态规划的题目全放出来,方便一次性查看。
动态规划背后的思想简单概括就是，若要解一个指定的问题，我们需要解它的不同部分问题(子问题)，再合并子问题求出最终想要的解。
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。每个阶段中，都求出本阶段的各个初始状态到过程终点的最短路径和最短距离，当逆序倒推到过程起点时，便得到了全过程的最短路径及最短距离，同时附带得到了一组最优结果。
1.递归+记忆化 ->反向推出递推公式
2.状态的定义 opt[n],dp[n].
3.状态转移的方程dp[n]=dp[n-1]+dp[n-2]
4.最优子结构
最经典的爬楼梯问题，给定一个数字代表着楼梯的层数，每次你可以走一步或者两步，求最终你可以有几种方式到达顶峰。递归是自上而下，一层层调用，到了递归的出口，又一层层的回来。而动态规划是从下而上的去思考，比如还是这个爬楼梯问题，如果是动态规划的思想就是
f[n]=f[n-1]+f[n+2];
//一个斐波那契数列动态规划需要大量的实战练习，一般你只要记住两步，定义好状态，有些时候单单定义一个一维数组的状态是不够的，二通过状态的定义推出递推公式。具体看场景使用。（下面是leetcode70，72,120，121，122，123，152，300动态规划的题目）
/**
* @param Integer $n
* @return Integer
*/
function climbStairs($n) {
if($n<=1){
return 1;
}
$res[0]=1;
$res[1]=1;
for($i=2;$i<=$n;$i++){
$res[$i]=$res[$i-1]+$res[$i-2];
}
return $res[$n];
}
/**
* @param String $word1
* @param String $word2
* @return Integer
*/
function minDistance($word1, $word2) {
for($i=0;$i<=strlen($word1);$i++) $dp[$i][0]=$i;
for($i=0;$i<=strlen($word2);$i++) $dp[0][$i]=$i;
for($i=1;$i<=strlen($word1);$i++){
for($j=1;$j<=strlen($word2);$j++){
if(substr($word1,$i-1,1)==substr($word2,$j-1,1)){
$dp[$i][$j]=$dp[$i-1][$j-1];
}else{
$dp[$i][$j]=min($dp[$i-1][$j],$dp[$i][$j-1],$dp[$i-1][$j-1])+1;
}
}
}
return $dp[strlen($word1)][strlen($word2)];
}
/**
* @param Integer[][] $triangle
* @return Integer
*/
function minimumTotal($triangle) {
if(empty(count($triangle))){
return 0;
}
for($i=count($triangle)-1;$i>=0;$i--){
for($j=0;$j<count($triangle[$i]);++$j){
$triangle[$i][$j] +=min($triangle[$i+1][$j],$triangle[$i+1][$j+1]);
}
}
return $triangle[0][0];
}
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
//二维数组的0，1，2表示的状态分别是没买股票，买了股票， 卖了股票
$res=0;
$pro[0][0]=$pro[0][2]=0;
$pro[0][1]=-$prices[0];
for($i=1;$i<count($prices);$i++){
$pro[$i][0]=$pro[$i-1][0];
$pro[$i][1]=max($pro[$i-1][1],$pro[$i-1][0]-$prices[$i]);
$pro[$i][2]=$pro[$i-1][1]+$prices[$i];
$res=max($res,$pro[$i][0],$pro[$i][1],$pro[$i][2]);
}
return $res;
}
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$dp[0][0]=0;
$dp[0][1]= -$prices[0];
$res=0;
for($i=1;$i<count($prices);$i++){
$dp[$i][0]=max($dp[$i-1][0],$dp[$i-1][1]+$prices[$i]);
$dp[$i][1]=max($dp[$i-1][1],$dp[$i-1][0]-$prices[$i]);
$res=max($dp[$i][0],$dp[$i][1],$res);
}
return $res;
}
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$res=0;
$dp[0][0][0]=0;
$dp[0][0][1]= -$prices[0];
$dp[0][1][0]= -$prices[0];
$dp[0][1][1]= -$prices[0];
$dp[0][2][0]=0;
for($i=1;$i<count($prices);$i++){
$dp[$i][0][0]=$dp[$i-1][0][0];
$dp[$i][0][1]=max($dp[$i-1][0][1],$dp[$i-1][0][0]-$prices[$i]);
$dp[$i][1][0]=max($dp[$i-1][1][0],$dp[$i-1][0][1]+$prices[$i]);
$dp[$i][1][1]=max($dp[$i-1][1][0]-$prices[$i],$dp[$i-1][1][1]);
$dp[$i][2][0]=max($dp[$i-1][2][0],$dp[$i-1][1][1]+$prices[$i]);
}
$length=count($prices)-1;
return max($res,$dp[$length][0][0],$dp[$length][1][0],$dp[$length][2][0]);
}
/**
* @param Integer[] $nums
* @return Integer
*/
function maxProduct($nums) {
$max=$min=$res=$nums[0];
for($i=1;$i<count($nums);$i++){
$mx=$max;
$mn=$min;
$max=max(max($nums[$i],$nums[$i]*$mx),$nums[$i]*$mn);
$min=min(min($nums[$i],$nums[$i]*$mx),$nums[$i]*$mn);
$res=max($res,$max);
}
return $res;
}
/**
* @param Integer[] $nums
* @return Integer
*/
function lengthOfLIS($nums) {
if(empty($nums)){
return 0;
}
$res=1;
for($i=0;$i<count($nums);$i++){
$dp[$i]=1;
for($j=0;$j<$i;++$j){
if($nums[$j]<$nums[$i]){
$dp[$i]=max($dp[$i],$dp[$j]+1);
}
$res=max($res,$dp[$i]);
}
}
return $res;
}
