网站建设列表横向,一流的企业网站建设,免费的网络推广渠道有哪些,宿州品牌网站建设公司Problem: 509. 斐波那契数 文章目录 思路解题方法复杂度Code解法一 #xff08;暴力搜索#xff09;解法二 #xff08;记忆化搜索#xff09;解法三#xff08;动态规划#xff09;解法四#xff08;动态规划#xff08;空间O(1)#xff09;#xff09; 思路 斐波那… Problem: 509. 斐波那契数 文章目录 思路解题方法复杂度Code解法一 暴力搜索解法二 记忆化搜索解法三动态规划解法四动态规划空间O(1) 思路 斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给定 n 请计算 F(n) 。 斐波那契数列是一个典型的递归问题但是直接使用递归会导致大量的重复计算因此我们可以使用动态规划的思想来优化。动态规划的核心思想是将大问题分解为小问题然后从小问题开始解决逐步解决大问题。 解题方法 1.暴力搜索直接使用递归公式进行计算但是这种方法存在大量的重复计算时间复杂度高不推荐使用。 2.记忆化搜索在暴力搜索的基础上使用一个数组来保存已经计算过的斐波那契数避免重复计算。 3.动态规划使用一个数组dp其中dp[i]表示第i个斐波那契数然后从小到大依次计算dp[i]最后返回dp[n]。 4.动态规划空间O(1)在动态规划的基础上进一步优化空间复杂度。由于dp[i]只与dp[i-1]和dp[i-2]有关因此我们只需要保存这两个状态无需保存整个dp数组。 复杂度
时间复杂度: 时间复杂度: O ( n ) O(n) O(n)需要遍历一次序列。 空间复杂度: 空间复杂度: O ( 1 ) O(1) O(1)只需要常数个变量。 Code
解法一 暴力搜索
class Solution {public int fib(int n) {if(n 0) {return 0;}if(n 1) {return 1;}return fib(n - 1) fib(n - 2);}
}解法二 记忆化搜索
class Solution {public int fib(int n) {int[] arr new int[n 1];Arrays.fill(arr, -1);return f(n, arr);}public int f(int n, int[] arr) {if(n 0) {return 0;}if(n 1) {return 1;}// 命中缓存if(arr[n] ! -1) {return arr[n];}int ans f(n - 1, arr) f(n - 2, arr);// 记录缓存arr[n] ans;return ans;}
}解法三动态规划
class Solution {public int fib(int n) {if (n 0) {return 0;}if (n 1) {return 1;}int[] dp new int[n 1];dp[1] 1;for(int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}解法四动态规划空间O(1)
class Solution {public int fib(int n) {if (n 0) {return 0;}if (n 1) {return 1;}int Lastlast 0, Last 1;for (int i 2, cur; i n; i) {cur Lastlast Last;Lastlast Last;Last cur;}return Last;}
}
