[数据结构与算法]剑指offer Java day07

T1 10- I. 斐波那契数列

动态规划

class Solution {
    public int fib(int n) {
        if(n==0) return 0;
        //因为本题只要求输出第n项斐波拉契数所以只用关心n-1和n-2，节约空间就声明3个变量
        int dp0 = 0;
        int dp1 = 1;
        int tmp;
        for(int i=2;i<=n;i++){
            tmp = (dp0+dp1)%1000000007;
            dp0 = dp1;
            dp1 = tmp;
        }
        return dp1;
    }
}

T2 10- II. 青蛙跳台阶问题

因为青蛙一次可以跳1或2，所以第n步是f(n-1),f(n-2)之和

可转为斐波拉契数组 不过初始条件是 f(1) = 1 f(2)=2

class Solution {
    public int numWays(int n) {
        if(n==0||n==1) return 1;
        int dp1 = 1;
        int dp2 = 2;
        int tmp = dp2;
        for(int i=3;i<=n;i++){
            tmp = (dp1+dp2) % 1000000007;
            dp1 = dp2;
            dp2 = tmp;
        }
        return tmp;
    }
}

T3 63. 股票的最大利润

前i日最大利润=max( 前(i?1)日最大利润 , 第i日价格?前i日最低价格 )
dp[i]=max( dp[i?1] , prices[i]?min(prices[0:i]) )

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE,profit=0;
        for(int price:prices){
            //前i日最低价格
            cost = Math.min(cost,price);
            //前i日最大利润
            profit = Math.max(profit,price-cost);
        }
        return profit;
    }
}