leetcode练习:动态规划 – 1

斐波那契数相关

结合动态规划分治、避免重叠子问题的思想来进行求解

剑指 Offer 10- I,II

两个问题都与斐波那契数列相关,以I为例,斐波那契数列可以通过递归实现,但要避免大量重复的运算,因此可以使用数组暂存。(自己写的就是丑陋了些)

    public static int fib(int n) {
        int[] res = new int[n+1];

        return fibHepler(n,res);
    }

    private static int fibHepler(int n,int[] res){
        if(n<=1) {
            res[n] = n;
            return n;
        }
        else {
            res[n-1] = res[n-1]!=0?res[n-1]:fibHepler(n-1,res);
            res[n-2] = res[n-2]!=0?res[n-2]:fibHepler(n-2,res);
            return res[n-1]+res[n-2];
        }
    }

其实可以避免递归

    int[] res = new int[n+1];
    res[0] = 0;
    res[1] = 1;

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

而通过推公式f(n) = f(n-1) + f(n -2) >> f(n+1) = f(n) + f(n-1)可以进一步简化问题。关键在于如何写来避免特殊情况。

        int a = 0, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;

引用

图解算法数据结构 - LeetBook - 力扣(LeetCode)全球极客挚爱的技术成长平台

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇