剑指Offer-第8天 动态规划（简单）

第一题

题目链接：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/

个人题解：迭代即可，可以减少空间复杂度，只需要使用常数级别的空间即可。

代码：

const int mod=1e9+7;
class Solution {
public:
    int fib(int n) {
        if(n<2) return n;
        int a=0,b=0,c=1;
        for(int i=2;i<=n;i++){
            a=b;
            b=c;
            c=(a+b)%mod;
        }
        return c;
    }
};

运行截图：

第二题

题目链接：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

个人题解：迭代即可，和上一题几乎一样

代码：

const int mod=1e9+7;
class Solution {
public:
    int numWays(int n) {
        if(n==0) return 1;
        if(n<=3) return n;
        int a=0,b=0,c=1;
        for(int i=1;i<=n;i++){
            a=b;
            b=c;
            c=(a+b)%mod;
        }
        return c;
    }
};

运行截图：

第三题

题目链接：https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/

个人题解：动态规划，找到现在为止的最小值与当前值的最大差值即可。

代码：

class Solution {
public:
    int maxProfit(vector& prices) {
        int maxn=0,minn=INT_MAX;
        for(auto x:prices){
            maxn=max(maxn,x-minn);
            minn=min(minn,x);
        }
        return maxn;
    }
};

运行截图：