动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。
力扣509题:斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1 F(n) = F(n – 1) + F(n – 2),其中 n > 1 给定 n ,请计算 F(n) 。
这个题目解法还是比较多的,主要说一下递归和动态规划
/** * @param {number} n * @return {number} */
var fib = function (n) {
// 动态规划
if (n == 0 || n == 1) {
return n
}
let prev1 = 0;
let prev2 = 0;
let result=1
for (let i = 2; i <= n; i++) {
prev2 = prev1
prev1 = result
result = prev1 + prev2
}
return result
// 递归暴力解法
if(n==0||n==1){
return n
}
return fib(n-1)+fib(n-2)
};
第一次提交是动态规划的算法,第二提交是递归算法,就代码来说递归看起来是简单很多,但是执行用时,动态规划的算法是要快很多的。
力扣1137题:泰波那契序列 Tn 定义如下:
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n,请返回第 n 个泰波那契数 Tn 的值。
/** * @param {number} n * @return {number} */
var tribonacci = function (n) {
if (n == 0) {
return 0
}
if (n <= 2) {
return 1
}
let prev1 = 1;
let prev2 = 1;
let prev3 = 0;
for (let i = 3; i < n; i++) {
let num = prev1 + prev2 + prev3
prev3 = prev2
prev2 = prev1
prev1 = num
}
return prev1 + prev2 + prev3
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/186050.html原文链接:https://javaforall.cn