动态规划（DP）

动态规划问题的一般形式就是求最值。比如求最长递增子列，最小编辑距离等等,求解动态规划的核心问题是穷举。

首先，动态规划的穷举有点特别，这类问题存在「重叠子问题」，穷举的话效率会极其低下，所以需要缓存来优化穷举过程，避免不必要的计算。
其次，动态规划问题一般有「最优子结构」，用子问题的最优解获得整个问题的最优解。
另外虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，只有列出正确的「状态转移方程」才能正确地穷举。

斐波那契数列

斐波那契数列的数学形式就是递归的，写成代码就是这样：

    public function dp($number)
    {
       if($number==1||$number==2){
           return 1;
       }
        return $this->dp($number - 1) + $this->dp($number- 2);
    }

这样写代码虽然简洁易懂，但是十分低效，当N比较大时递归层数太深时间复杂度为 O(2^n)，很明显算法低效的原因：存在大量重复计算，比如 f(n) 被计算了多次，这就是动态规划问题的第一个性质：重叠子问题。
带缓存的递归解法
即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

class SequenceDP
{
    public $array;

    public function __construct($number)
    {
        for ($i = 0; $i < $number + 1; $i++) {
            $this->array[$i] = -1;
        }
    }

    public function dp($number)
    {
       if($number==1||$number==2){
           return 1;
       }
        if ( $this->array[$number] != -1) 
        return $this->array[$number];
        return $this->dp($number - 1) + $this->dp($number- 2);
    }
}

$xx = new SequenceDP(10);
$int = $xx->dp(10);
var_dump($int);

细节优化

据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个数组来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

function fib($n) {
    if ($n == 2 || $n == 1) 
        return 1;
    $prev = 1, $curr = 1;
    for ($i = 3;$i <=$n; $i++) {
        $sum = $prev + $curr;
        $prev = $curr;
        $curr = $sum;
    }
    return $curr;
}

凑零钱的问题

下面我们来深入了解凑零钱的问题

给你 n 种面值硬币，面值分别为 a, b ... ，e，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额 ?

很明显这个问题是动态规划问题，因为它具有「最优子结构」。子问题是互相独立，互不干扰的。
我们首先确定正确的状态转移方程
状态是原问题和子问题中变化的变量，由于硬币数量无限，所以唯一的状态就是金额 amount，所有函数每次变化为dp(amount),分析出伪代码如下：

# 要凑出金额 n，至少要 dp(n) 个硬币
function dp(n){
    # 遍历所有面值，选择需要硬币最少的那个结果
    for coin in coins:
            res = min(res, 1 + dp(n - coin))
    return res
}

PHP代码实现如下：

<?php

class Coin
{
    public $values = [1, 5, 10, 50];
    public function dp($amount)
    {
        $return = $amount;
        if ($amount < 0) {
            $return = -1;
        }elseif ($amount = 0)) {
            $return = 0;
        } elseif (in_array($amount, $this->values)) {
            $return = 1;
        } else {
            foreach ($this->values as $v) {
                //能够凑的面值则凑
                if ($v < $amount) {
                    $return_temp = 1 + $this->dp($amount - $v);
                    //如果当前凑个数更少则返回
                    if ($return_temp < $return) {
                        $return = $return_temp;
                    }
                }
            }
        }
        return $return;
    }
}
$xx = new Coin();
$int = $xx->dp(65);
var_dump($int);

至此，状态转移方程其实已经完成了，以上算法已经是暴力解法了，但是效率堪忧，以下是数学形式就是状态转移方程：

观察发现子问题总数是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度是指数级别。我们也可以自底向上使用 DP缓存数组 来消除重叠子问题，
DP缓存数组定义:$array[i] = x 表示当目标金额为 i 时，至少需要 x 枚硬币。初始化为-1表示未计算过。

<?php

class Coin
{
    public $values = [1, 5, 10, 50];
    public $array;

    public function __construct($amount)
    {
        for ($i = 0; $i < $amount + 1; $i++) {
            $this->array[$i] = -1;
        }
    }

    public function dp($amount)
    {
        $return = $amount;
        if ($amount < 1) {
            $return = 0;
        } elseif ($amount = 0)) {
            $return = 0;
        } elseif ($this->array[$amount] != -1) {
            $return = $this->array[$amount];
        } elseif (in_array($amount, $this->values)) {
            $return = 1;
        } else {
            foreach ($this->values as $v) {
                //能够凑的面值则凑
                if ($v < $amount) {
                    $return_temp = 1 + $this->dp($amount - $v);
                    //如果当前凑个数更少则返回
                    if ($return_temp < $return) {
                        $return = $return_temp;
                    }
                }
            }
        }
        $this->array[$amount] = $return;
        return $return;
    }
}

$coin = new Coin(12111);
$int = $coin->dp(12111);
var_dump($int);