算法--动态规划算法

定义

• 动态规划是属于运筹学的数学方法，主要用于求解某类最优化问题。一般情况下如果某个问题由多个交叠的子问题构成，并且子问题可由更小的子问题递推得到时，就可以采用动态规划来求解。求解动态规划问题最重要的就是找到递推表达式。

算法案例：数组求最大和

• 已知一个整数数组 num=[1,5,3,7,9,3,4]，从数组中取出若干个数求和，并且取出的数两两不相邻，获取其中最大的和。动态规划可以简单地理解为选或不选的问题。
  以下题为例：
  首先我们假设当我们取到第 i 个数时，最大和为 dp(i)

  
  image.png

当 i 为 6 时，此时有两种情况，如果选择第六个则和为前四个数最大和加上第六个数，如果不选为前五个数的最大和。以此类推下去便可以得到上图，值完善了右边的部分，由图中可以看出左侧部分和右侧是有重复的，因此我们只需要将每次的计算结果保存在一个数组中便可以免去不必要的重复计算，因此可以得出以下的递推公式

image.png

• PHP代码实现

function rob($nums) {
    $max = [$nums[0], max($nums[0], $nums[1])];
    
    for ($i = 2; $i < count($nums); $i++)
    {
        $max[$i] = max(($nums[$i] + $max[$i - 2]), $max[$i - 1]);
    }
    return $max[count($nums) - 1];
}

特性

在用递归法自顶向下求解问题时，每次产生的子问题并不总是新的子问题，有些子问题是反复被求解过的，因此我们将每次子问题的结果保存下来，下次直接获取其值，不用再次计算。
其他案例代码