leetcode——动态规划

 `明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case`

一、斐波那契数列(506/)

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

1、递归计算（复杂度高，指数级别）(超时)时间复杂度：O(2^N)

class Solution {
    public int fib(int N) {
        if(N==0 || N==1) return N;
        if(N==2) return 1;
        return fib(N-1)+fib(N-2);
    }
}

缺点：重叠子问题多，比如f(18)算了两次，复杂度为指数级别

2、带备忘录的递归O(N)

class Solution {
    public int fib(int N) {
        if(N<2) return N;
        int [] dp =new int[N+1];
        dp[1]=1;
        for(int i=2;i<=N;i++){
            dp[i]=dp[i-1]+dp[i-2];  
   }
    return dp[N];     
    }
}

二、爬楼梯，青蛙台阶（70/10）

这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。
第i阶可以由以下两种方法得到： 在第 (i-1)阶后向上爬1阶。 在第 (i-2) 阶后向上爬 2 阶。 令 dp[i] 表示能到达第 i阶的方法总数： 函数dp[i]=dp[i−1]+dp[i−2]

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];   }
}

class Solution {
    public int numWays(int n) {    
    if (n <=1) return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= 1000000007;//题目取模原因
        }
        return dp[n];   
    }
}