MATLAB 动态规划

小嗷犬2023-02-052023-08-25

什么是动态规划

动态规划是一种数学优化方法，它是一种在给定约束条件下，求解最优化问题的方法。动态规划的基本思想是将原问题分解为若干个子问题，先求解子问题的最优解，然后根据子问题的最优解，求解原问题的最优解。

动态规划的步骤通常为：

将原问题分解为子问题
确定状态
确定一些初始状态（边界状态）的值
确定状态转移方程

思想上类似于递归，但动态规划采用记录子问题的最优解的方法，避免了重复计算子问题的最优解，从而提高了计算效率；除此之外，动态规划通常采用自底向上的方法，而递归通常采用自顶向下的方法。

斐波那契数列

斐波那契数列作为递归算法的经典教学案例也可以用动态规划来解决，并且效率更高。

递归算法

function f = fib(n)
    if n == 1 || n == 2
        f = 1;
    else
        f = fib(n-1) + fib(n-2);
    end
end

计算 fib(40) ：

1 2	`>> tic; fib(40); toc 历时 9.110819 秒。`

计算 fib(400) ：

1 2	`>> tic; fib(100); toc % 超过5分钟，主动停止`

动态规划算法

function f = fib(n)
    f = zeros(1, n);
    f(1) = 1;
    f(2) = 1;
    for i = 3:n
        f(i) = f(i-1) + f(i-2);
    end
    f = f(n);
end

计算 fib(40) ：

1 2	`>> tic; fib(40); toc 历时 0.000180 秒。`

计算 fib(400) ：

1 2	`>> tic; fib(400); toc 历时 0.003652 秒。`

以上时间数据仅为单次执行得出的结果，可能具有一定的随机性，但是我们仍能看出，动态规划算法的效率要远远高于递归算法。

跳台阶

跳台阶问题描述如下：

有一个台阶，一次可以跳1级或2级，求跳上n级台阶有多少种跳法。

解题思路：

类似于斐波那契数列，我们可以用动态规划来解决这个问题。

将原问题分解为子问题：跳上n级台阶的跳法数 = 跳上n-1级台阶的跳法数 + 跳上n-2级台阶的跳法数
确定状态：设跳上n级台阶的跳法数为f(n)
确定一些初始状态（边界状态）的值：f(1) = 1, f(2) = 2
确定状态转移方程：f(n) = f(n-1) + f(n-2)

动态规划代码实现：

function f = jump(n)
    f = zeros(1, n);
    f(1) = 1;
    f(2) = 2;
    for i = 3:n
        f(i) = f(i-1) + f(i-2);
    end
    f = f(n);
end

计算 jump(100) ：

1 2	`>> tic; jump(100); toc 历时 0.001638 秒。`

接雨水

题目链接：LeetCode 42 题：接雨水

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例2：

输入：height = [4,2,0,3,2,5]
输出：9

解题思路：

将原问题分解为子问题：对于每个柱子，能接的雨水量 = min(当前柱子及其左边最高柱子高度, 当前柱子及其右边最高柱子高度) - 当前柱子高度；第i个柱子及其左边最高柱子高度 = max(第i-1个柱子左边最高柱子高度, 第i个柱子高度)，当前柱子及其右边最高柱子高度同理。
确定状态：设当前柱子及其左边最高柱子高度为leftMax[i]，当前柱子及其右边最高柱子高度为rightMax[i]。
确定一些初始状态（边界状态）的值：leftMax[1] = height[1]，rightMax[n] = height[n]。
确定状态转移方程：leftMax[i] = max(leftMax[i-1], height[i])，rightMax[i] = max(rightMax[i+1], height[i])。

动态规划代码实现：

function r = rain(height)
    n = length(height);
    leftMax = zeros(1, n);
    rightMax = zeros(1, n);
    leftMax(1) = height(1);
    rightMax(n) = height(n);
    for i = 2:n
        leftMax(i) = max(leftMax(i-1), height(i));
        rightMax(n-i+1) = max(rightMax(n-i+2), height(n-i+1));
    end
    r = sum(min(leftMax, rightMax) - height);
end

计算 rain([0,1,0,2,1,0,1,3,2,1,2,1]) ：

1 2	`>> tic; rain([0,1,0,2,1,0,1,3,2,1,2,1]); toc 历时 0.005192 秒。`