动态规划(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);

规划

下篇文章讲继续学习最长递增子列最小编辑距离

讨论数量: 0

慎思笃行