动态规划算法java代码_动态规划算法解决背包问题

动态规划算法java代码_动态规划算法解决背包问题JavaScript动态规划,斐波那契数,泰波那序契列

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

动态规划的基本概念

动态规划(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
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/186050.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号