Sword finger offer 10 Ⅰ 10Ⅱ. 63 dynamic planning (simple)

10.Ⅰ

subject :

The finger of the sword Offer 10- I. Fibonacci sequence https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

idea : F(N) = F(N - 1) + F(N - 2), Recursive time complexity is too high , Use dynamic programming , Move ab.

Code :

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

result :

10.Ⅱ

subject :

The finger of the sword Offer 10- II. The problem of frog jumping on the steps https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

 

  idea :( Steal a picture )

  still fib problem , It's just f(0)=f(1)=1.

Code :

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

result :

63.

subject :

The finger of the sword Offer 63. The biggest profit of stocks https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/

idea :( Steal a picture )

Remember to buy at the cheapest time !

Code :

// violence   Time complexity is too high 
class Solution {
    public int maxProfit(int[] prices) {
        int max=0;
        for(int i=prices.length-1;i>=0;i--){
            for(int j=i-1;j>=0;j--){
                int tmp=prices[i]-prices[j];
                if(tmp>max)  
                    max=tmp;
            }
        }
        return max;
    }
}

//DP. Buy at the lowest price 
class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int max=0;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<min)
                min=prices[i];
            else if(prices[i]-min>max)
                max=prices[i]-min;
        }
        return max;
    }
}

result :