动态规划是一种数学优化方法,它是一种在给定约束条件下,求解最优化问题的方法。动态规划的基本思想是将原问题分解为若干个子问题,先求解子问题的最优解,然后根据子问题的最优解,求解原问题的最优解。
动态规划的步骤通常为:
思想上类似于递归,但动态规划采用记录子问题的最优解的方法,避免了重复计算子问题的最优解,从而提高了计算效率;除此之外,动态规划通常采用自底向上的方法,而递归通常采用自顶向下的方法。
斐波那契数列作为递归算法的经典教学案例也可以用动态规划来解决,并且效率更高。
function f = fib(n)
if n == 1 || n == 2
f = 1;
else
f = fib(n-1) + fib(n-2);
end
end
计算 fib(40)
:
>> tic; fib(40); toc
历时 9.110819 秒。
计算 fib(400)
:
>> 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)
:
>> tic; fib(40); toc
历时 0.000180 秒。
计算 fib(400)
:
>> tic; fib(400); toc
历时 0.003652 秒。
以上时间数据仅为单次执行得出的结果,可能具有一定的随机性,但是我们仍能看出,动态规划算法的效率要远远高于递归算法。
跳台阶问题描述如下:
有一个台阶,一次可以跳1级或2级,求跳上n级台阶有多少种跳法。
解题思路:
类似于斐波那契数列,我们可以用动态规划来解决这个问题。
动态规划代码实现:
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)
:
>> tic; jump(100); toc
历时 0.001638 秒。
题目描述:
给定 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
解题思路:
动态规划代码实现:
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])
:
>> tic; rain([0,1,0,2,1,0,1,3,2,1,2,1]); toc
历时 0.005192 秒。
免责声明:本文系网络转载或改编,未找到原创作者,版权归原作者所有。如涉及版权,请联系删