算法

2024-06-14 10:58| 来源: 网络整理| 查看: 265

前言

最近在牛客网上做了几套公司的真题，发现有关动态规划（Dynamic Programming）算法的题目很多。相对于我来说，算法里面遇到的问题里面感觉最难的也就是动态规划（Dynamic Programming）算法了，于是花了好长时间，查找了相关的文献和资料准备彻底的理解动态规划（Dynamic Programming）算法。一是帮助自己总结知识点，二是也能够帮助他人更好的理解这个算法。后面的参考文献只是我看到的文献的一部分。

动态规划算法的核心

理解一个算法就要理解一个算法的核心，动态规划算法的核心是下面的一张图片和一个小故事。

这里写图片描述

A * "1+1+1+1+1+1+1+1 =？" * A : "上面等式的值是多少" B : *计算* "8!" A *在上面等式的左边写上 "1+" * A : "此时等式的值为多少" B : *quickly* "9!" A : "你怎么这么快就知道答案了" A : "只要在8的基础上加1就行了" A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

由上面的图片和小故事可以知道动态规划算法的核心就是记住已经解决过的子问题的解。

动态规划算法的两种形式

上面已经知道动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：①自顶向下的备忘录法 ②自底向上。为了说明动态规划的这两种方法，举一个最简单的例子：求斐波拉契数列**Fibonacci **。先看一下这个问题：

Fibonacci (n) = 1; n = 0 Fibonacci (n) = 1; n = 1 Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)

以前学c语言的时候写过这个算法使用递归十分的简单。先使用递归版本来实现这个算法：

public int fib(int n) { if(n

【本文地址】

公司简介

联系我们