/* 爬楼梯：动态规划 */
int climbingStairsDP(int n) {
  if (n == 1 || n == 2)
    return n;
  // step1: 初始化dp 表，用于存储子问题的解
  vector<int> dp(n + 1);
  // step1: 确定初始状态：预设最小子问题的解
  dp[1] = 1;
  dp[2] = 2;
  // step3:确定状态转移方程，进行状态转移：从较小子问题逐步求解较大子问题
  for (int i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];//状态转移方程
  }
  return dp[n];
}

  class Solution {
    public:
        int climbStairs(int n) {
            // n个阶梯对应多少种方法(一共n+1个元素)，也就是状态dp
    
            if(n<3)//要大于等于3才适用于动态规划的问题～
                return n;
    
            // 时间复杂度O（N），空间复杂度为O（N）
    
            // step1：定义dp表
            int dp[n+1];//n个状态，对应n+1数组
    
            // step2：定义初始状态
            dp[0]=0;
            dp[1]=1;
            dp[2]=2;//一次性两级，或两次1级,故此有两种方法
    
            // step3：状态转移方程
            for(int i=3;i<n+1;i++)//注意数组是到n+1
            {
                //第n级。有n-1或n-2决定
                dp[i]=dp[i-1]+dp[i-2];//状态转移方程。
            }
    
            return dp[n];//最后返回第n阶梯的时候的解决方案
        }
    };

/* 爬楼梯最小代价：动态规划 */
int minCostClimbingStairsDP(vector<int> &cost) {

  int n = cost.size() - 1;

  if (n == 1 || n == 2)
    return cost[n];

  // 初始化 dp 表，用于存储子问题的解
  vector<int> dp(n + 1);

  // 初始状态：预设最小子问题的解
  dp[1] = cost[1];
  dp[2] = cost[2];

  // 状态转移：从较小子问题逐步求解较大子问题
  for (int i = 3; i <= n; i++) {
    dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
  }

  return dp[n];
}

  class Solution {
    public:
        int fib(int n) {
    
            //首先只有大于2才适用
            if(n<2)
                return n;
            
            //step1：定义dp表及下标的含义。
            //状态就是当前在第几个数，选择就是前面两个数的和
            int dp[n+1]; //对应于状态n
    
            // step2：状态的初始化
            dp[0]=0;
            dp[1]=1;
    
            // step3:自下而上遍历，推到状态方程
            for(int i=2;i<n+1;i++)
            {
                dp[i]=dp[i-1]+dp[i-2];//后面的每一项数字都是前面两项数字的和
            }
    
            return dp[n];
    
        }
    };

  class Solution {
    public:
        int fib(int n) {
    
            //首先只有大于2才适用
            if(n<2)
                return n;
            
            return fib(n-1)+fib(n-2);
    
        }
    };

  class Solution {
    public:
        int fib(int n) {
    
            //首先只有大于2才适用
            if(n<2)
                return n;
            
            //step1：定义dp表
            // int dp[n+1]; //对应于状态n
    
            // step2：状态的初始化
            // dp[0]=0;
            // dp[1]=1;
            int dp_i_2=0;
            int dp_i_1=1;
    
            // step3:自下而上，推到状态方程
            for(int i=2;i<n+1;i++)
            {
                // dp[i]=dp[i-1]+dp[i-2];//后面的每一项数字都是前面两项数字的和
                int dp_i=dp_i_1+dp_i_2;
    
                // 滚动更新
                dp_i_2=dp_i_1;
                dp_i_1=dp_i;
            }
    
            // return dp[n];
            return dp_i_1;
    
        }
    };

  class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
    
            // step1：定义dp表。状态变量应该就是n=nums.size()了吧，也是唯一的变量
            int n=nums.size();
            int dp[n];
    
            // step2：确定初始状态
            for(int i=0; i<n;i++)
            {
                dp[i]=1;//自身，长度就是1了
            }
    
            // step3:状态转移方程
            // 对于状态dp[i]。以及在i前的状态j。
            // 若nums【i】>nums【j】.那么dp【i】为dp【i】（其他值）与dp【j】+1之间的最值
            int max_len=1;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(nums[i]>nums[j]) //注意nums只能访问到n-1
                        dp[i]=max(dp[i], dp[j]+1);//循环的其他j也参与了对比的。只是只记录最大值
                }
                max_len=max(max_len,dp[i]);//dp[i]为最大的
            }
    
            return max_len;//不能直接返回dp[n-1]，因为这是n-1位置时最大的，不是全部最大的~
        }
    };