动态规划算法(Dynamic Programming)是一种通过将原问题分解为相对简单的子问题的方式求解复杂问题的高效算法。这种算法的核心思想是避免重复计算已经解决的子问题。
比如著名的斐波那契数列、爬楼梯、最小路径和等问题都可以用动态规划算法求解。
适用条件
1
最优化原理(最优子结构性质):一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2
无后效性:将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态施加影响。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。
3
子问题的重叠性:动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时间。
动态规划解决问题的步骤
定义状态
动态规划中的“状态”可以说是父问题和所有子问题对应的结果,如:爬楼梯问题中,爬到第十层楼梯的爬法数是第十层的状态,爬到第二十层楼梯的爬法是第二十层的状态,以此类推。
推导状态转移方程
所谓的状态转移方程,其实类似于数学中的归纳法。拿斐波那契数列为例,我们定义数列中的第n个数字是f(n)【这里的f(n)代表的含义即是第一步中的状态】。那么根据数列的定义可以很轻易推出转移方程是f(n) = f(n-1) + f(n-2),在已知f(1)=1,f(2)=1的情况下,就可以一直类推下去获得结果。
初始条件和边界值确定
还是拿上面的数列为例,初始条件就是前几项可以很容易推得的状态,边界值则最小是0,最大是n,这个n可以是10也可以是100,视题目要求而定。
具体题解
斐波那契数列
问题描述:斐波那契数列是指这样一个数列:1,1,2,3,5,8,13,21,34,55,89……这个数列从第3项开始 ,每一项都等于前两项之和。求第n个数是多少?
JS写法
function fib(n) {
if (n === 1 || n === 2) return n;
// 初始化 dp 表,用于存储子问题的解 const dp = new Array(n + 1).fill(-1);
// 初始状态:预设最小子问题的解 dp[1] = 1; dp[2] = 2;
// 状态转移:从较小子问题逐步求解较大子问题
for (let i = 3; i <= n; i++) {
dp[i] = dp[i – 1] + dp[i – 2];
}
return dp[n];
}
因为我们所求的第n项永远只和它的前一、前二项有关,并不需要用一整个dp表来存储状态,所以本题还可以在空间利用上做出优化,优化后代码如下:
function fib(n) {
if (n === 1 || n === 2) return n;
// 相当于dp表中的n-1项和n-2项
let a = 1, b = 2;
for (let i = 3; i <= n; i++) {
// 只保留关键状态,“滚动”前进
const tmp = b;
b = a + b;
a = tmp;
}
return b;
}
动态规划是一种强大的算法设计技术,已经在许多领域得到了应用。
随着计算能力的提升和算法研究的深入,在未来可能会看到更多关于动态规划的并行化和分布式计算的研究,以进一步提高其性能和效率。
同时,随着机器学习和人工智能的发展,动态规划可能会与这些领域更紧密地结合,创造出新的可能性和应用。
✦✦
由于微信公众号修改了推送规则,
没有加“星标★”的订阅号,
收到的推送只有标题和小图,
而且会慢慢收不到最新的推送。
想要不错过各类讯息,
小伙伴们可以将【乐科科集团】公众号
加个星标❤
你 “在看” 我吗?