PHP-动态规划入门

2020-04-27 本文已影响0人简单方式

动态规划入门

动态规划是什么

一句话概括就是 通过历史数据推导出现有数据 避免重复计算，一般通过 $dp[n]$ , $dp[n][n]$ , 一维或者二维数组来保存计算结果

什么问题能用动态规划

(1) 问题的答案依赖于问题的规模，随着规模变大答案本身也不断变大.

(2) 大规模问题通过小规模问题答案递推得来，就是不断通过旧数据计算新数据以此类推得出答案.

动态规划解题三步骤

(1) 定义数组含义，用来保存历史数据，比如 $dp[0]$ $dp[1]$ $dp[n]$ 代表保存什么值

(2) 找出递推关系式，如斐切那波数列 $dp[n]$ = $dp[n-1]$ + $dp[n-2]$ 一次类推

(3) 找出初始值，如 $dp[0]$ = 1 $dp[1]$ = 1 得出 $dp[2]$ = $dp[2-1]$ + $dp[2-2]$

一句话概述就是，解题步骤是将大问题分解成小问题，通过小问题在递推成大问题

例题一 (最大子序和)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
要求 O(n)

解题

(1) 定义数组保存历史数据
$dp[n]$ 代表每一次累加最大值

(2) 找出关系式
如果一个值那就是 $dp[i]$ = $dp[0]$
如果两个值那就是 $dp[i]$ = $dp[i-1]$ > 0 ? $dp[i]$ + $dp[i-1]$ : $dp[0]$

(3) 找出边界值
可以看到每次都是 i-1 ，所以要保证 $dp[n]$ 至少有两个值，如果只有一个，则直接反馈

代码

class Solution
{
    /**
     * @param Integer[] $dp
     * @return Integer
     */
    public function maxSubArray($dp)
    {
        $size = count($dp);

        if ($size == 1) {
            return $dp[0];
        }

        $max = $dp[0];

        for ($i = 1;$i < $size;$i++) {
            $dp[$i]   = $dp[$i - 1] < 0 ? $dp[$i] : $dp[$i - 1] + $dp[$i];
            $max      = $dp[$i] > $max ? $dp[$i] : $max;
        }

        return $max;
    }
}

测试

  $obj  = new Solution();
  $max = $obj->maxSubArray([-2,1,-3,4,-1,2,1,-5,4]);
  echo $max; //输出 6
  exit;

例题二 (打家劫舍)

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例一
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)
偷窃到的最高金额 = 1 + 3 = 4 。

示例二
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，
接着偷窃 5 号房屋 (金额 = 1)
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题

(1) 定义数组保存历史数据
$dp[n]$ 代表当前房间数最大盗窃金额

(2) 找出关系式
如果一个房间 $dp[0]$ = $dp[0]$
如果两个房间 $dp[1]$ = max( $dp[0]$ , $dp[1]$ )
如果三个房间 $dp[3]$ = max( $dp[n-2]$ + $nums[n]$ , $dp[n-1]$ )

(3) 确定边界值
可以看到上面的关系式，只有当三个房间才可以满足状态转移方程，所以如果只有一个或者两个房间，直接返回即可.

代码

class Solution
{
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    public function rob($nums)
    {
        if(empty($nums)){
            return 0;
        }

        $dp   = [];
        $size = count($nums);

        if ($size == 1) {
            return $nums[0];
        }

        if ($size == 2) {
            return max($nums[0], $nums[1]);
        }

        $dp[0] = $nums[0];
        $dp[1] = max($nums[0], $nums[1]);

        for ($i = 2;$i < $size;$i++) {
            $dp[$i] = max($dp[$i - 2] + $nums[$i], $dp[$i - 1]);
        }

        return $dp[$size - 1];
    }
}

测试

  $obj  = new Solution();
  $max = $obj->rob([2, 1, 1, 2]);
  echo $max; //输出 4 [(2+2) = 4]
  exit;

结束

动态规划确实是很多适用问题的最优解，核心只是一行状态转移公式，却可以代替很多无用的重复计算，达到时间复杂度最优.