算法-动态规划-java

这篇具有很好参考价值的文章主要介绍了算法-动态规划-java。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划

动态规划的核心

哪些不记得过去的人,都注定要重蹈覆辙
(因为要记录过去的事情,所以是典型的空间换时间)
算法-动态规划-java,算法,动态规划,java

动态规划算法的两种形式

上面已经知道动态规划算法的核心是记住已经求过的解,记住求解的方式有两种:
①自顶向下的备忘录法 ②自底向上。
举一个最简单的例子,使用斐波那契数列来理解

首先使用递归的方法实现这个算法
public int fib(int n)
{
	if(n<=0)
		return 0;
	if(n==1)
		return 1;
	return fib( n-1)+fib(n-2);
}
//输入6
//输出:8

使用递归数,分析一下递归算法的执行流程,假如输入6,递归树如下:
算法-动态规划-java,算法,动态规划,java
上面的递归树中的每一个子节点都会执行一次,很多重复的节点被执行,fib(2)被重复执行了5次。由于调用每一个函数的时候都要保留上下文,所以空间上开销也不小。这么多的子节点被重复执行,如果在执行的时候把执行过的子节点保存起来,后面要用到的时候直接查表调用的话可以节约大量的时间。下面就看看动态规划的两种方法怎样来解决斐波拉契数列数列问题。

①自顶向下的备忘录法
public class FibonacciMemoization {
    public static int Fibonacci(int n) {
        if (n <= 1)
            return n;
//这里为什么开辟空间的时候需要length+1,因为在求最优解的时候会用到Memo[0]
//到后边还有更清晰的图解
        int[] Memo = new int[n + 1];
        for (int i = 0; i <= n; i++)
            Memo[i] = -1;

        return fib(n, Memo);
    }

    public static int fib(int n, int[] Memo) {
        if (Memo[n] != -1)
            return Memo[n];

        Memo[n] = fib(n - 1, Memo) + fib(n - 2, Memo);

        return Memo[n];
    }

    public static void main(String[] args) {
        int n = 6;
        int result = Fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

备忘录法也是比较好理解的,创建了一个n+1大小的数组来保存求出的斐波拉契数列中的每一个值,在递归的时候如果发现前面fib(n)的值计算出来了就不再计算,如果未计算出来,则计算出来后保存在Memo数组中,下次在调用fib(n)的时候就不会重新递归了。比如上面的递归树中在计算fib(6)的时候先计算fib(5),调用fib(5)算出了fib(4)后,fib(6)再调用fib(4)就不会在递归fib(4)的子树了,因为fib(4)的值已经保存在Memo[4]中。

②自底向上的动态规划(推荐使用)

备忘录法还是利用了递归,上面算法不管怎样,计算fib(6)的时候最后还是要计算出fib(1),fib(2),fib(3)…,那么何不先计算出fib(1),fib(2),fib(3)…,呢?这也就是动态规划的核心,先计算子问题,再由子问题计算父问题。

public class FibonacciDP {
    public static long calculateFibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        long[] fibArray = new long[n + 1];
        fibArray[0] = 0;
        fibArray[1] = 1;

        for (int i = 2; i <= n; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
        }

        return fibArray[n];
    }

    public static void main(String[] args) {
        int n = 6; // 想要计算的斐波那契数列的项数
        long result = calculateFibonacci(n);
        System.out.println("第 " + n + " 项斐波那契数列的值为: " + result);
    }
}

一般来说由于备忘录方式的动态规划方法使用了递归,递归的时候会产生额外的开销,使用自底向上的动态规划方法要比备忘录方法好。

更好的理解动态规划

经典例题:钢条分割

算法-动态规划-java,算法,动态规划,java

首先使用递归的方法实现这个算法
public static int cut(int []p,int n)
	{
		if(n==0)
			return 0;
		int q=Integer.MIN_VALUE;
		for(int i=1;i<=n;i++)
		{
			q=Math.max(q, p[i-1]+cut(p, n-i));	
		}
		return q;
	}

递归很好理解,如果不懂可以看上面的讲解,递归的思路其实和回溯法是一样的,遍历所有解空间但这里和上面斐波拉契数列的不同之处在于,在每一层上都进行了一次最优解的选择,q=Math.max(q, p[i-1]+cut(p, n-i));这个段语句就是最优解选择,这里上一层的最优解与下一层的最优解相关。

①自顶向下的备忘录法
public static int cutMemo(int []p)
	{
		int []r=new int[p.length+1];
		for(int i=0;i<=p.length;i++)
			r[i]=-1;						
		return cut(p, p.length, r);
	}
	public static int cut(int []p,int n,int []r)
	{
		int q=-1;
		if(r[n]>=0)
			return r[n];
		if(n==0)
			q=0;
		else {
			for(int i=1;i<=n;i++)
				q=Math.max(q, cut(p, n-i,r)+p[i-1]);
		}
		r[n]=q;
		
		return q;
	}

有了上面求斐波拉契数列的基础,理解备忘录方法也就不难了。备忘录方法无非是在递归的时候记录下已经调用过的子函数的值。这道钢条切割问题的经典之处在于自底向上的动态规划问题的处理,理解了这个也就理解了动态规划的精髓。

②自底向上的动态规划(推荐使用)
public static int buttom_up_cut(int []p)
	{
		int []r=new int[p.length+1];
		for(int i=1;i<=p.length;i++)
		{
			int q=-1;
			//①
			for(int j=1;j<=i;j++)
				q=Math.max(q, p[j-1]+r[i-j]);
			r[i]=q;
		}
		return r[p.length];
	}

自底向上的动态规划问题中最重要的是理解注释①处的循环,这里外面的循环是求r[1],r[2]…,里面的循环是求出r[1],r[2]…的最优解,也就是说r[i]中保存的是钢条长度为i时划分的最优解,这里面涉及到了最优子结构问题,也就是一个问题取最优解的时候,它的子问题也一定要取得最优解。下面是长度为4的钢条划分的结构图。
从这个图也能理解,为什么r开辟空间的时候需要p.length+1,因为在求最优解的时候会用到r[0]
算法-动态规划-java,算法,动态规划,java文章来源地址https://www.toymoban.com/news/detail-722322.html

到了这里,关于算法-动态规划-java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Java实现】动态规划算法解决01背包问题

    1、问题描述: 一个旅行者有一个最多能装m公斤的背包,现在有n中物品,每件的重量分别是W1、W2、……、Wn,每件物品的价值分别为C1、C2、……、Cn, 需要将物品放入背包中,要怎么样放才能保证背包中物品的总价值最大? 2、动态规划算法的概述 1)动态规划(Dynamic Progra

    2023年04月09日
    浏览(53)
  • (Java) 算法——动态规划 最长公共子序列 图解

    遇到了用动态规划来求解最长公共子序列问题,算法这块儿比较薄弱,便想着在网上找现成的思路和代码,也算拾人牙慧,但有一点没想到,都已经22年了,关于LCS问题网上给出的答案如此一言难尽……,只有零散几篇对于 新手 来说比较友好,但也仅仅这样,好在自己花了点

    2023年04月08日
    浏览(47)
  • Java数据结构与算法----动态规划(背包篇)

    1.1.算法思路 0/1背包是动态规划、背包问题中最经典的问题啦!它主要的问题是: 给定n种物品、这n种物品的重量分别是,价值分别是 ,而你有一个容量为C的背包,请问如何求出所能拿的最大价值呢? 对于动态规划,我们先需要找到一条推导公式,然后确定边界: 我们设

    2024年02月07日
    浏览(49)
  • java实现0-1背包问题方案(动态规划-贪心算法-回溯-分支定界)

    动态规划算法时间复杂度较低,能够求解较大规模的问题,但空间复杂度较高,不适用于数据量较大的问题。 贪心算法时间复杂度较低,能够求解较大规模的问题,但不能保证求得的解是最优解。 回溯算法能够求解较小规模的问题,但时间复杂度较高,不适用于数据量较大

    2024年02月01日
    浏览(122)
  • Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心

    1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解, 然后综合各个小问题,得到最终答案。 2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。 3、迭代法(Iterative Method) 无法使用公式一次求解,而需要使用重复结构

    2024年02月08日
    浏览(43)
  • 算法题——华为OD机试——整数划分排序/员工分月饼——动态规划——Java

    一个考察动态规划的机试题的数学模型建立,和两种思路的取舍 公司分月饼,m个员工,买了n个月饼,m = n,每个员工至少分一个月饼,但是也可以分到多个,单人分到最多月饼的个数是Max1,单人分到第二多月饼个数是Max2。 但需要满足Max1-Max2 = 3,单人分到第n-1多月饼个数是

    2024年03月16日
    浏览(53)
  • Java数据结构与算法:动态规划之斐波那契数列

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里,让我们一同探讨Java中的动态规划,重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法,通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(47)
  • 【华为OD机试】找数字(动态规划算法—Java&Python&C++&JS实现)

    本文收录于专栏:算法之翼 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年04月10日
    浏览(77)
  • 【课设】java:迷宫小游戏(递归与分治、动态规划、贪心算法、回溯法、分支限界法)

    鱼弦:CSDN内容合伙人、CSDN新星导师、全栈领域优质创作者 、51CTO(Top红人+专家博主) 、github开源爱好者(go-zero源码二次开发、游戏后端架构 https://github.com/Peakchen) 递归与分治算法 原理: 递归与分治算法将问题分解为子问题,递归地解决每个子问题,最后将结果合并得到整

    2024年02月02日
    浏览(39)
  • 298.【华为OD机试】跳格子三(动态规划算法—Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年04月15日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包