0119 动态规划 Day8

剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5

class Solution {
    public int fib(int n) {

    }
}

解题思路

动态规划解析：
状态定义：设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列第 i 个数字。
转移方程： dp[i + 1] = dp[i] + dp[i - 1] ，即对应数列定义 f(n + 1) = f(n) + f(n - 1) ；
初始状态： dp[0] = 0， dp[1] = 1，即初始化前两个数字；
返回值： dp[n] ，即斐波那契数列的第 n 个数字。

循环求余法：
大数越界：随着 n 增大, f(n) 会超过 Int32 甚至 Int64 的取值范围，导致最终的返回值错误。

求余运算规则：设正整数 x, y, p ，求余符号为 ⊙，则有 (x + y) ⊙p = (x ⊙ p + y⊙ p) ⊙ p

解析：根据以上规则，可推出 f(n) ⊙p = [f(n-1)⊙ p + f(n-2) ⊙ p]⊙p，从而可以在循环过程中每次计算 sum = (a + b)⊙1000000007，此操作与最终返回前取余等价。

代码如下

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;
    }
}

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1

class Solution {
    public int numWays(int n) {

    }
}

解题思路

设跳上 n 级台阶有f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况：跳上 1 级或 2 级台阶。

当为 1 级台阶：剩 n−1 个台阶，此情况共有 f(n−1) 种跳法；
当为 2级台阶：剩 n-2个台阶，此情况共有f(n−2) 种跳法。

即 f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2) ，以上递推性质为斐波那契数列。因此，本题可转化为求斐波那契数列第 n 项的值，与斐波那契数列等价，唯一的不同在于起始数字不同。

代码如下

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;
    }
}

剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution {
    public int maxProfit(int[] prices) {

    }
}

解题思路

动态规划解析：

状态定义：设动态规划列表 dp ，dp[i] 代表以prices[i] 为结尾的子数组的最大利润（以下简称为前 i日的最大利润）。

转移方程：由于题目限定 “买卖该股票一次” ，因此前 i 日最大利润 dp[i] 等于前 i - 1日最大利润 dp[i−1] 和第 i 日卖出的最大利润中的最大值。
dp[i] = max(dp[i - 1], prices[i] - min(prices[0:i]))

即前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)

初始状态： dp[0] = 0 ，即首日利润为 0 ；
返回值： dp[n - 1]，其中 n为 dp列表长度。

代码如下

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}