58同城网站建设问题,官方网站侵权,便宜自适应网站建设,自己的网站没有域名文章目录题目描述思路 代码递归动态规划二刷题目描述
呃#xff5e;说来尴尬#xff0c;在简单题栽跟头了 #xff08;超时#xff09;一般来说#xff0c;这玩意是递归教学题了。但实际上会有很多重复的冗余步骤#xff0c;实际上用动态规划效率会更高
思路 代码递归动态规划二刷题目描述
呃说来尴尬在简单题栽跟头了 超时一般来说这玩意是递归教学题了。但实际上会有很多重复的冗余步骤实际上用动态规划效率会更高
思路 代码
递归
class Solution {public int fib(int n) {if(n 0 || n 1){return n;}return (fib(n - 1) fib(n - 2)) % 1000000007;}
}动态规划
O(n) O(n)
class Solution {int[] ans new int[101];public int fib(int n) {// O(n) O(n) 的动态规划ans[0] 0;ans[1] 1;for(int i 2; i n; i){ans[i] ans[i - 1] ans[i - 2];ans[i] % 1000000007;}return ans[n];}
}O(n) O(1) 因为这道题实际上只要记录当前两个元素的状态即可因此实际上可以用两个变量起到整个数组的作用。
class Solution {public int fib(int n) {// O(n) O(1) 的动态规划int a 0;int b 1;int sum 0;for(int i 1; i n; i){sum (a b) % 1000000007;a b;b sum;}return a;}
}二刷
边界和返回值还是值得注意的
class Solution {public int fib(int n) {int pre 0, now 1, next 0;for(int i 1; i n; i) {next (pre now) % 1000000007;pre now;now next;}return pre;}
}
