动态规划《一》

1、斐波那契数列（暴力递归）

int fib(int N){
  
if(N == 1 || N==2){
    return 1;
  }
return flib(N-1)+flib(N-2);
}

• 递归树
  f(20)
  f(19) f(18)
  f(18) f(17)
  ...
  时间复杂度为 O(2^n)，指数级别

动态规划问题的第一个性质：重叠子问题

带备忘录的递归解法

int fib(int N){
  if(N < 1){
  return 0 ;
}
vector<int>memo(N+1,0);
return helper(memo,N);
}

int helper(vector<int>& memo ,int n){
if(n ==1 || n == 2) return 1;
//已经计算过了
if(memo[n] != 0){
  return memo[n];
}
memo[n] = helper(memo,n-1)+helper(memo,n-2);
return memo[n];
}

dp 数组的迭代解法

int fib(int N){
vector<int> dp(N+1,0);
//base
dp[1]= dp[2] =1;
for(int i=3;i<=N;i++){
  dp[i]=dp[i-1]+dp[i-2];
}
return dp[N];
}