动态规划

algorithm

---

最长连续递增子序列

• 最长连续递增子序列
• 题目大意：在一个数字序列中找到最长的且连续的递增子序列的长度。
• 例如：序列：$[1,3,5,4,7]$ 最长连续子序列长度为3，即$[1,3,5]$
• 又如: 序列：$[2,2,2,2,2]$ 最长连续子序列长度为1，即$[2]$

1、思路一

• 计算每个元素开始或者结束的连续子序列，记录最大的值

int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return n;
        int maxlen = 1;
        for(int i = 0; i < n;i++ )  {
            int len = 1;// 每次nums[i] 开始的序列最大长度为1,往后增长
            for(int j = i+ 1;j < n;j++){
            if(nums[j] > nums[j-1] ) {// 连续递增
                len += 1; // 长度增加
                maxlen = max(maxlen,len);
            }else {// 不连续递增了，下一个元素继续计算
                break;
            }
        }
        return maxlen;
    }

2、思路2

• 假设我们知道了某个元素结尾的最长连续子序列的长度，那么下一个元素，要么比其前一个元素大，一起构成更长的一个连续子序列，要么自己独自成一个子序列长度为1。
• 假设我们有$dp[i]$ 表示以$nums[i]$结尾元素的最长连续子序列长度
• 那么下一个元素$nums[i+1]$ 与$nums[i]$ ，要么$nums[i+1] > nums[i]$ 这时可以构成一个更长的连续递增子序列且以$nums[i+1]$结尾，长度为$dp[i] + 1$。要么$nums[i+1] \le nums[i]$，这时以$nums[i+1]$结尾的最长连续子序列长度为1.
• 初始状态是：$dp[0] = 1$
• 综合上述两种情况，可以得到如下的表达式

$$dp[i+1] = \left\{\begin{matrix} dp[i] +1 & if & nums[i+1] > nums[i] \\ 1 & else \end{matrix}\right.$$

int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return n;
        vector<int> dp(n,1);
        int maxlen = 1;
        for(int i = 1; i < n; i++ )  {
            if( nums[i] > nums[i-1] ) {
                dp[i] = dp[i-1] + 1 ;
            }
            maxlen = max( dp[i] , maxlen );
        }
        return maxlen;
    }

• 时间复杂度：O(n)，空间复杂度：O(n)
• 由于只需要获取最长的长度，所以这里可以优化空间复杂度

---

最长递增子序列

• 最长递增子序列
• 题目的意思是：在一个数字序列中找到最长的且是递增的子序列，返回这个最长子序列的长度
• 与上一个不同的是，这里的序列不需要是连续的
• 例如：$[10,9,2,5,3,7,101,18]$ 序列的最长递增子序列为$[2,3,7,101]$

1、思路1

• 由上一题的思路可以知道，如果知道$nums[i]$ 结尾的最长递增子序列为$dp[i]$ 那么，以$nums[i+1]$ 结尾的最长子序列，肯定是i+1前面的某个子序列（可能为空）以$num[k]$结尾，加上$nums[i+1]$构成的。也可以从另一个角度理解，如果$i+1$前面的某个数$nums[k]$ 满足：$nums[k] \lt nums[i+1]$， 那么，$\{nums[k],nums[i+1]\}$可以构成一个比原来更长的子序列。
• 初始状态：$dp[0] = 1$
• 综合上述说明：可以得到如下的递推公式
  $$dp[i] = \underset{0 \leqslant k< i }{max}\left\{\begin{matrix} dp[k] + 1 & if & nums[i] > nums[k] \end{matrix}\right.$$

int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1 )
            return n;
        vector<int> dp(n,1);// 初始化为1
        int max_len = 1;
        for(int i = 1 ;i < n; i++) {
            for(int j = i-1 ;j >=0 ;j-- ) { // 遍历[0,i-1]的元素加上nums[i] 之后的长度是否构成更长的递增子序列
                if(nums[j] < nums[i]) {
                    dp[i] = max(dp[i],dp[j] + 1 );
                    max_len = max(max_len,dp[i]);
                }
            }
        }
        return max_len;
    }

• 时间复杂度：O($n^2$)，空间复杂度:O(n)
  

最长递增子序列的数量

• 最长递增子序列的个数
• 题目大意：在第二题的基础上，找到所有长度等于最大长度的递增子序列的长度的个数
• 例如：$[1,3,5,4,7]$，最长递增子序列的个数为2， 即，$[1, 3, 4, 7]$ 和 $[1, 3, 5, 7]$。又如：$[2,2,2,2,2]$，最长递增子序列的个数为5，所有的长度为1的序列都是最长递增子序列

1、思路1

• 上一题中记录了最长递增子序列的长度。并没有记录这个长度的子序列的个数
• 所以我们通过计算每一个元素为结尾的最长递增子序列的来源个数，来获得最大长度递增子序列的个数
• 具体的来说，假设$f[i]$表示以$nums[i]$结尾的元素的最长子序列个数，$dp[i]$表示以$nums[i]$结尾的最长子序列的长度，那么找到最长的子序列长度$dp[k]$，就可以找到其对应的长度来源的个数$f[k]$。那么$f[k]$如何计算呢？
• $f[k]$ 依赖于$dp[k]$，如果$dp[k]$是从$dp[m]$扩展而来，那么$f[k] = f[m]$，如果$dp[k]$还可以从$dp[x]$扩展而来，那么$f[k] = f[m] + f[x]...$可以看出来，$f[k]$等于能够从之前的某个子序列扩展到$dp[k]$而来的所有序列个数之和。
• 得到如下的公式:
• 初始情况：$dp[i] =1,f[i]=1$;
  $$dp[i] = \underset{0 \leqslant k< i }{max}\left\{\begin{matrix} dp[k] + 1 & if & nums[i] > nums[k] \end{matrix}\right. \\ f[i] = \sum_{ nums[i] > nums[k] \&\& dp[k] + 1 == dp[i] } f[k]$$
• 最后需要依据最大长度的递增子序列求和所有的来源个数。

int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1)
            return n;
        vector<int> dp(n,1); // nums[i]结尾的最长递增子序列长度
        int max_len = 1;//最大长度
        vector<int> max_c(n,1);// 每个最长子序列的长度默认为1
        for(int i = 1; i < n; i++ ){                                 
            for(int j = i - 1; j >= 0; j-- ) {
                if(nums[i] > nums[j]) {
                    if(dp[i] < dp[j] + 1){// dp[i] 可以从dp[j] 扩展得到更长的子序列，那么最长子序列的个数就是扩展前dp[j]的个数，max_c[j]
                        max_c[i] = max_c[j]; // 扩展后的来源个数
                    }else if(dp[i] == dp[j] + 1) { // 相同长度的其他扩展而来的子序列 
                        max_c[i] += max_c[j] ; // 因为长度相同，所以求和来源的个数
                    }
                    dp[i] = max(dp[i],dp[j] + 1);
                    max_len = max(dp[i],max_len);
                }
            }
        }
        // 遍历所有的dp[i]等于最大长度时，求和所有的max_c[i]，得到最大长度递增子序列的个数和
        int maxc = 0;
        for(int i = 0; i < n ; i++) {
            if(dp[i] == max_len) {
                maxc += max_c[i];
            }
        }
        return maxc;
    }

• 时间复杂度：O($n^2$)；空间复杂度：O(n)
  

最长配对链

• 最长配对链
• 题目大意：给定元素为两个数的元组的数组，元组的属性$(a,b) a < b$，如果两个元素$x=(a,b),y=(c,d)$ 满足$b<c$ 那么$(x,y)$构成一个链，长度为2，这个题求的是所有元素中能够成这个链的最大长度。其中元素序列可以任意选取。

思路1

• 本题与最长递增子序列非常相似，不同点在于，这里可以随意选取元素，构成组合，如果按照元组的第一个元素排序，就能够得到和最长递增子序列的问题一致的情况。
• 初始情况：$dp[i] = 1$;

int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        if(n <= 1)
            return n;
        sort(pairs.begin(),pairs.end(),[](vector<int>& a,vector<int>&b ){return a[0] < b[0];});
        vector<int> dp(n,1);
        int max_len = 1;
        for(int i =1;i < n; i++) {
            int ifirst = pairs[i][0];
            for(int j =i -1 ;j >= 0; j--) {
                if(pairs[j][1] < ifirst) { // 构成递增链
                    dp[i] = max(dp[i],dp[j] + 1); //更新递增链大小
                    max_len = max(max_len,dp[i]);
                }
            }
        }
        return max_len;
    }

• 时间复杂度：O($n^2$) 空间复杂度：O(n)
  

子数组等差数列的个数

• 子数组等差数列的个数
• 题目大意：给定一个数组，数组里存在等差数列，等差数列满足如下条件:存在$0 \le P \lt Q \lt N$，连续序列$A[P],A[p+1] \cdots A[Q]$ 满足$A[i] - A[i-1] ，P+1 \lt i \lt Q$为一定值。

思路1

• 对于任意两个下标(i,j)我们判断这个序列是否是等差数列。
• 一个等差数列必定是有一个小的等差数列扩展而来。就像最长回文序列一样，从最基本的情况，两个元素，扩展到多个元素。

int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        if(n <= 2 )
            return 0;
        vector<vector<int> > dp(n,vector<int>(n,0));
        for(int i = 1; i < n-1; i++) {
            dp[i-1][i+1] = (A[i] -A[i-1] == A[i+1] -A[i] );
        }
        for(int k = 3; k < n ;k++ ) {
            for(int i = 0; i < n; i++ ) {
                int j = i + k;
                if(j >= n)
                    break;
                dp[i][j] = dp[i][j-1] && (A[j] - A[j-1] == A[j-1] - A[j-2]);
            }
        }
        int c = 0;
        for(int i =0 ;i < n; i++) {
            for(int j = i+2;j < n; j++) {
                if(dp[i][j] == 1)
                    c += 1;
            }
        }
        return c;
}

• 时间复杂度：$O(n^2)$，空间复杂度：$O(n^2)$
  

子序列的最长等差数列长度

• 子序列最长的等差数列
• 题目大意：给定一个数组，里面能够选择一些数字构成等差数列，那么构成的等差数列中，最长的长度是多少？

思路1

• 长度大于3的一个等差数列的特征是，除去最后一个数，前面的等差数列仍然构成等差数列，并且长度减1，所以和最长递增子序列的思考方式类似，对于每一个元素，我们判断这个元素是否可以加到前面的某个序列中构成一个更长的序列。
• 假设$dp[i][j]$表示以$A[i],A[j]$结尾的等差序列的最大长度，那么可以得到如下的公式
  $$dp[i][j] = \underset{0\le k \lt i\lt j}{max}\{dp[k][i] + 1 \ if A[j] - A[i] == A[i] - A[k]$$
• 对于$A[i],A[j]$结尾的序列，我们遍历$k,0\le k \lt i \lt j$

int longestArithSeqLength(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n,vector<int>(n,2));
        for(int i = 0; i < n; i++ ) {
            dp[i][i] = 0;
        }
        int maxlen = 2;
        for(int i = 1; i < n; i++ ) {
            for(int j = i + 1; j <n ; j++) {
                int ak =   2*A[i] - A[j]; // 查找A[j] - A[i] == A[i] - A[k]
                for(int k = 0; k < i ;k++) {
                    if(A[k] == ak) {
                        dp[i][j] = max(dp[i][j] , dp[k][i] + 1 );
                        maxlen = max(dp[i][j],maxlen);
                    }
                }
            }
        }
        return maxlen;
}

• 时间复杂度：$O(n^3)$，空间复杂度：$O(n^2)$
• 可以优化对$k$的查找
  

等差子序列的个数

• 等差子序列的个数
• 题目大意：给定一个数组，找到所有的可以构成等差数列的序列个数
• 举例说明：$[2, 4, 6, 8, 10]$，有等差子序列
  $[2,4,6] [4,6,8] [6,8,10] [2,4,6,8] [4,6,8,10] [2,4,6,8,10] [2,6,10]$

思路1

• 构成等差序列的来源必定是另个一等差数列。与上一题类似，我们假设$dp[i][j]$ 表示以$A[i],A[j]$ 结尾的等差数列的个数，那么$dp[i][j]$必然是从另个等差数列构建而来，$A[i] - A[k] == A[j] - A[i]$， 所有满足上述条件的$k$认为是等差数列的来源，我们对所有满足上述条件的$k$求和，得到子序列来源个数。

$$dp[i][j] = \sum_{0\le k\lt i \lt j} \{dp[k][i] + 1\} \ if \ A[j] - A[i] = A[i] - A[k]$$

• 初始个条件$dp[i][j] = 0$

int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        int sum = 0;
        for(int i = 0; i < n; i++ ) {
            for(int j = i + 1; j < n; j++ ) {
                // int ak = 2*A[i] - A[j]; // mind overflow !!!
                long t = A[j];
                t -= A[i];
                for(int k = 0; k < i; k++ ) {
                    long x = A[i];
                    x  -= A[k];
                    if(t == x  ) {
                        dp[i][j] += dp[k][i] + 1;
                    }
                }
                sum += dp[i][j];
            }
        }
        return sum;
}

• 时间复杂度：$O(n^3)$，空间复杂度:$O(n^2)$
• 注意可能会有溢出
  

二维问题

最小的赢得游戏代价

• 猜游戏的代价
• 题目大意：给定范围内的数$[1-n]$，一个人选择一个候选数，让游戏者猜这个数。
• 游戏者猜测一个数x。知道候选数的人，给出游戏者关于猜测数字与候选数的结果，比候选数大或者小，或者相等
• 1）如果猜对了（相等），不需要付出代价
• 2）如果猜错了（大或者小），需要付出$x$代价
• 问：在$[1-n]$ 中，如果游戏者保证能赢，也就是最后一定能够猜对数字，需要的代价最小是多少？

题目理解及思路

• 题目的意思是，对于某个候选数，猜对的方式有多种多样，比如二分猜测，顺序猜测。但是代价是不一样的。这时，需要找到一个代价，使得所有的猜测方法，付出的代价不大于这个代价。
• 其次对于所有的候选数，我们要使得我们获得的代价最小。
• 在所有候选数的中，单个能保证赢的情况下，最小化所有的代价。比较绕。。
• 此题，与Google面试题，扔鸡蛋类似。
• 给定n,求在这个限定内的总最小代价，那么，猜测可以从某个数$1 \le k \le n$猜测，对的代价为0，高的代价为$k + [1...k-1]代价$，低的代价为$k + [k+1,n]的代价$，由此我们假设$dp[i][j]$ 表示从$[i,j]$ 不论候选数什么，我们猜测代价，保证一定能够猜对时的最小代价

$$dp[i][j] = \underset{i\lt k \lt j}{min} \{max{(dp[i][k-1] , dp[k+1][j] )} + k\}$$

• 其中，$max$表示我们在特定策略下，最保险的代价，即在选择一个数开始猜，接着选择第二个数直到最后猜对候选数的最大代价。
• 策略有多种。策略指的是先猜那一个数。比如先猜中间的数，这个策略会有多个不同的代价，为什么？因为在这个基础上，下一轮猜测也有多种方式，对一个候选数来说，有时猜开头的数，比猜中间的数代价要小。
• 举个例子,$[1,2,3,4,5,6,7]$ 中，假设候选数为1，第一次选中间数，4，高了。第二次，选择中间2，代价为4+2，如果第二次选择1，代价为4+0，可以看到两次选择代价是不一样的。
• 所以在$[i,j]$范围内，我们不管猜测的策略是什么样，(先猜一个数，然后再猜另一个数...)，只要遍历所有的第一猜数情况，选择最小($min$)的一个作为,$[i,j]$范围内的最小代价，就能够保证，我们不会付出大于$dp[i][j]$的代价，就能够完全才对候选数。
• 初始条件：$dp[i][i] = 0,dp[i][i+1] = i$

int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));// 默认最大代价
        for(int i = 1;i < n ; i++) {
            dp[i][i+1] = i; // 初始情况步长为1
            dp[i][i] = 0;
        }
        dp[0][0] = 0;
        dp[n][n] = 0;
        int k = 2;// 步长为2
        for(int k =2 ;k <= n; k++ ) {
            for(int i = 1;i <= n; i++) {
                int j = i + k;// [i,j]范围内
                if(j > n)
                    break;
                int mincost = INT_MAX;
                for(int m = i+1; m < j;m++) { // [i,m-1],[m+1,j]
                    int t  =  max(dp[i][m-1],dp[m+1][j]) + m; // 选择猜测m,之后的最保险策略（能够猜到候选数的最大代价，付出这个代价，无论第二步，第三步，怎么猜测，一定能够找到候选数）
                    mincost = min(mincost,t); // 选择一个最小，最为[i,j]的猜测代价
                }
                dp[i][j] = mincost;
            }
        }
        return dp[1][n]; // 返回[1,n]最小代价
}

• 时间复杂度：$O(n^3)$,空间复杂度：$O(n^2)$

预测胜利者

• 预测胜利者
• 题目大意：一个数组，数组里存放分数，两个选手，每次只能选择一个数字，可以从数组两端选择。已选择的数，不能再选。问给定一个数组，选手一，先选，是否有一种方法能够保证自己最后选择的所有数字之和大于对手。
• 假设两个游戏者都是从最大化自己收益，考虑做决策的。
• 题目也还是比较绕

bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        int sum = 0;
        for( int i = 0; i < n; i++ ) {
            dp[i][i] = nums[i];
            sum += nums[i];
        }
        for( int k = 1; k < n; k++ ) {
            for( int i = 0; i < n; i++ ) {
                int j = i + k ;
                if(j >= n )
                    break;
                int ni = min(getij (dp,i+1,j-1),getij(dp,i+2,j)) + nums[i];
                int nj = min(getij(dp,i+1,j-1),getij(dp,i,j-2)) + nums[j];
                dp[i][j] = max( ni ,nj );
            }
        }
        return dp[0][n-1] >= sum - dp[0][n-1];
}
int getij(vector<vector<int>>& dp,int i,int j) {
    int n = dp.size();
    if( i >= n || j >= n || i < 0 || j < 0 || i > j )
        return 0;
    return dp[i][j];
}

• 时间复杂度：$O(n^2)$ ，空间复杂度：$O(n^2)$
  

石头游戏

• 石头游戏
• 题目大意：多堆石头，排成一行，每次只能选择开始或者结束的一堆石头，假设alex先选择，问alex是否在游戏结束时，选择的石头数之和大于对手。
• 假设两个对手，每次选择都是从自己角度出发，最大化收益的。

思路1

• 假设两个人是公平选择数，且每次都是选择利于自己的。
• 单纯的从一个选手来考虑，如果$A[1...n]$ 中，如果我选择1，那么下一次，我能选择的情况，取决于对手选择的数，如果对手选择2，那么这个问题，缩小为$A[3...n]$，如果对手选择n,那么这个问题缩小为$A[2...n-1]$，如何定义从用数学形式来表达这个问题呢？
• 由于涉及到子问题，需要用前后两个标记来表达，所以我们假设dp[i][j]表示选手1在$A[i...j]$中，最好的选择，也就是石头最多的选择方案，先不管这个方案是什么样的。相当于在当前这步，看到了未来。而实际求解的时候却是从当前推导未来的。
• 那么有上面的分析，可以得到$dp[i][j]$ 在$i < j$的情况下，依赖两种情况，一种是$dp[i+1][j-1]$，一种是$dp[i+2][j]$
• 这里对于选手1来说只要选取在这两种情况下，可以获得最大的石头数即可。

$$dp[i][j] = max\left\{\begin{matrix} A[i] + max(dp[i+1][j-1],dp[i+2][j])& (i+1,j-1) &\&\& \ (i+2 ,j) & is \ valid \ index && player1 \ select\ A[i]\\ A[j] + max(dp[i][j-2],dp[i+1][j-1])& (i,j-2) &\&\& \ (i+1 ,j-1) & is \ valid \ index && player1 \ select \ A[j] \end{matrix}\right.$$

bool stoneGame(vector<int>& piles) {
        int m = piles.size();
        // int n = piles[0].size();
        vector<vector<int>> dp(m,vector<int>(m,0));
        int sum = 0;
        for(int i = 0 ;i < m ;i++) {
            sum += piles[i];
        }
        for(int k = 1; k < m ;k+=2) {
            for(int i = 0 ;i < m;i++) {
                int j = i + k  ;
                if(j >= m)
                    break;
                int front = piles[i] + max(getij(dp,i+1,j-1),getij(dp,i+2,j) );
                int end = piles[j] + max(getij(dp,i,j-2) , getij(dp,i+1,j-1) );
                dp[i][j] = max(front,end);
            }
        }
        return sum - dp[0][m-1] < dp[0][m-1];
}
int getij(vector<vector<int>>& dp,int i ,int j){
    int m = dp.size();
    if(i < 0  || j >= m || i >= m || j < 0)
        return 0;
    return dp[i][j];
}

• 时间复杂度:$O(n^{2})$,空间复杂度：$O(n^2)$
  

完美平方数个数

• 完美平方数个数
• 题目大意：一个数可以表示为多个平方数之和，例如$12=2^2+2^2+2^2=3^2+1^2+1^2+1^2$，当然还有其他方式表示。这两种方法中，第一个表示方法需要的平方数是3个，第二个是4个，题目求的是，给定一个数字，找到能够用平方数表示的最小的个数。

思路1

• 首先看下基础的情况，$1=1^2,2=1^2+1^2,3=1^2+1^2+1^2,4=2^2=1^2+1^2+1^2+1^2$，能够看到，一个数一定ne能够表示为平方数，因为有1这个平方数存在，所有的数都可以表示为$\sum_{1}^{n}1^2$，我们每次计算数n时，会首先想到n的表示方式等于n-1的表示方式，加1，这里的1表示用1^2来表示一个平方数。
• 所以我们假设$f[n]$：表示n可以被完全平方数表示的最小完全平方数的个数。
• 那么，$f[n]$可以看做是，$f[n - k^2] + 1$ 这里$k$表示，其平方小于$n$的某个平方数,我们只要遍历k就能够得到所有的表示方式选择一个最小的，为什么不从1开始一直遍历到n呢？这样肯定能够找到最小的表示方式。
• 原因在于，直接的想法是，n如果能够表示为前面一个数的平方，所用的数只需要加1，这里的完全平方数个数最小。

$$f[n] = \underset {1 \le k \le sqrt(n)} {min} f[n-k^2] +1$$

• 初始条件：$f[1] = 1$

int numSquares(int n) {
        if(n <= 0)
            return 0;
        if(n == 1)
            return 1;
        vector<int> dp(n+1,0);
        dp[1] = 1;
        for(int i = 2;i <= n; i++ ) {
            int m = int(sqrt(i)); // 不会超过这
            int t = INT_MAX;
            for(int k = 1 ;k <= m;k++){ // 从1开始遍历
                int j = k * k;
                t = min(dp[i-j] +1 ,t);//最小值
            }
            dp[i] = t;
        }
        return dp[n];
    }

• 时间复杂度:$O(n*n^{1/2})$,空间复杂度：$O(n)$

最长斐波那切数列

• 最长斐波那切数列
• 题目大意：给定一个递增数组，找出可以构成斐波那切序性质的数列的最大长度。斐波那切数列性质为:$A[j] = A[k] + A[i] ,k \lt i \lt j$
• 例如给定:$[1,2,3,4,5,6,7,8]$，中子序列：$[1,2,3,5,8]$ 满足斐波那切的性质，所以最大长度为5。又如：$[1,3,7,11,12,14,18]$，满足斐波那切数列性质的子序列有$[1,11,12]$, $[3,11,14]$ or $[7,11,18]$ ，所以最大长度为3。

思路0

• 从定义可以看出，斐波那切数列的最小长度为3，因为至少三个数才能满足，$A[j] = A[k] + A[i] ,k \lt i \lt j$，而且如果前两个数已经确定的话，第三个数，也是确定的。
• 反过来思考，如果我已经知道最后两个数，那么我需要找到一个数，是否在这两个数之前，并且满足斐波那切数列性质。
• 因为我们需要确定两个数作为一个状态，那么我们可以假设$dp[i][j]$ 表示以$(A[i],A[j]),i \lt j$结尾的斐波那切数列。
• 那么这个值与前面的以其他数字结尾的序列的关系是什么呢？
• 以$(A[i],A[j])$ 结尾的序列最大值，要么是没有构成最大值，要么是能够与$(A[k],A[i])$结尾的序列构成一个更长的斐波那切序列。所以，对于k我们只需要遍历$[0,i-1]$内的所有值，检查是否能够和$A[j]$ 一起构成更长的序列。

$$dp[i][j] = \left\{\begin{matrix} \underset{ 0\le k \lt i}{max} \{dp[k][i] + 1 & if \ A[k] + A[i] = A[j] \\ 2 & if \ A[k] + A[i] \ne A[j] \end{matrix}\right.$$
- 初始状态:$d[i][i] = 0,dp[i][j] = 2 \ i \ne j$

思路1-暴力搜索

• 基于上述的分析，对$k$ 执行搜索

// n^3
int lenLongestFibSubseq(vector<int>& A) {
    int n = A.size();
    vector<vector<int>> dp(n,vector<int>(n,2));// 除自己与自己外，所有的序列长度默认为2
    int maxlen = 0;
    for(int i = 0; i < n; i++ ) {
        dp[i][i] = 0; // 自己与自己构成的序列长度设置为0
        for(int j = i + 1; j< n; j++ ) { // (A[i],A[j])
            for(int k = 0; k < i; k++ ) { // 对k执行搜索，0<= k < i
                if(A[i] + A[k] == A[j]) { // A[j] 与(A[k],A[i])可以构成更长的序列
                    dp[i][j] = max(dp[i][j],dp[k][i] + 1);
                    maxlen = max(maxlen,dp[i][j]);
                }
            }
        }
    }
    return maxlen;
}

• 时间复杂度:$O(n^3)$,空间复杂度：$O(n^2)$
• 此题对于数组A长度为$10^3$超时，大约$10^8$为1s

思路2

• 使用二分查找
• 搜索k的范围是$[0,i-1]$ 并且数组A是严格递增的，那么我们查找$A[k] = A[j] - A[i]$
• 由于需要知道$A[k]$存在的下标，我们这里使用lower_bound函数，可以在返回值中判断是否存在$A[k]$

int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n,vector<int>(n,2));
        int t,maxlen = 0;
        for(int i = 0;i < n; i++) {
            dp[i][i] = 0;
            for(int j = i+1; j< n; j++) {
                int ak = A[j] - A[i];
                auto loc = lower_bound(A.begin(),A.begin() + i,ak); // 查找A[k]
                if(*loc == ak) {
                    int k = loc - A.begin();
                    dp[i][j] = max(dp[i][j],dp[k][i] + 1);
                    maxlen = max(maxlen,dp[i][j]);
                }
            }
        }
        return maxlen;
    }

• 时间复杂度:$O(n^2log(n))$,空间复杂度：$O(n^2)$

思路3

• 使用hashmap
• 基于上述的两种方法，我们可以在查找$A[k]$的时候进行优化，这里提前把$A[k]$的值与下标存储起来，查找时，如果存在直接获取下标。使用到hashmap

int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n,vector<int>(n,2));
        int t,maxlen = 0;
        unordered_map<int,int> umap;
        for(int i = 0; i < n; i++ ) {
            umap[A[i]] = i; // 存储所有的值与下标
            dp[i][i] = 0;
        }
        for(int i = 0;i < n; i++) {
            for(int j = i + 1; j< n; j++) {
                int ak = A[j] - A[i];
                auto e = umap.find(ak); // 查找A[k]
                if(e != umap.end() && e->second < i ) { // be careful the e->second < i 
                    int k = e->second;
                    dp[i][j] = max(dp[i][j], dp[k][i] + 1);
                    maxlen = max(maxlen, dp[i][j]);
                }
            }
        }
        return maxlen;
    }

• 这里需要注意的一点是，由于map是存储了所有的数据，查找的$A[k]$很可能是在$i$之后的一个数据，因为$A[j] - A[i]$的值可能是大于$A[i]$的，这里特别注意。
• 时间复杂度:$O(n^2)$,空间复杂度：$O(n^2)$
  

最长摆动序列

• 最长摆动序列
• 题目大意：给定一个数组，定义摆动数组的含义：相邻两个数的差值与前一个两个数的差值数值符号相异，或者相邻两个数的差值构成的数组，连续数组元素正负交替。举个例子：$[1,7,4,9,2,5]$，就是一个摆动数组，因为构成的差值数组$[6,-3,5,-7,3]$,差值数组的相邻元素正负交替。
• 可以看出来，摆动数组中的一个数，要么前面的数比它小，要么比它大，也就是一个数，要么是上摆，比相邻的两个数都要大，要么是下摆，比相邻的两个数都要小。

思路1

• 在一个数组中找出满足摆动数据的元素，构成一个新的数组，并满足摆动数组条件。
• 对原始数组中的任何一个数，假设它是摆动数组的一个元素，那么这个数需要满足什么条件呢？或者说这个数在摆动数组里是什么样的角色呢？即上文所说是上摆，还是下摆？
• 所以对原始数组的数，若想成为摆动数组的一个元素，构成更长的一个摆动数组，必须考虑两种情况，一种是：和之前摆动数组末尾元素，比自己小的数组，自己作为上摆元素，自己是比相邻数要大。一种是：和之前摆动数组尾元素，比自己大的，自己作为下摆元素，自己要比相邻元素小。所以一个数结尾的摆动数组有两种可能，一种是：自己作为下摆元素，一种是自己是上摆元素。
• 依据以上分析，我们假设$dp[i]={len1,len2}$，表示以$a_i$结尾的元素构成摆动数组的长度，其中$len1,len2$分别表示上摆和下摆的长度。可以得到如下的递推关系式：
  $$dp[i] = \left\{\begin{matrix} len1= & \underset{ 0\le j \lt i}{max} \{dp[j].len2 + 1 & if \ a_j \lt a_i \ \\ len2= & \underset{ 0\le j \lt i}{max} \{dp[j].len1 + 1 & if \ a_j \gt a_i \ \\ \end{matrix}\right.$$
• 初始化：$dp[i] = \{1,1\}, 0 \le i \lt n$

int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n <= 0)
            return 0;
        vector<vector<int>> dp(n,vector<int>());
        for(int i = 0 ;i < n; i++ ) {
            dp[i] = {1,1};
        }
        int maxlen = 1;
        for( int i = 1; i < n; i++ ) {
            for( int j = i - 1; j >=0; j-- ) {
                if(nums[j] > nums[i]) { // 构成上摆数组
                    dp[i][1] = max(dp[i][1] ,dp[j][0] + 1);
                }else if( nums[j] < nums[i] ) { // 构成下摆数组
                    dp[i][0] = max(dp[i][0] ,dp[j][1] + 1);
                }
                maxlen = max(maxlen,dp[i][0]);
                maxlen = max(maxlen,dp[i][1]);
            }
        }
        return maxlen;
}

• 时间复杂度：$O(n^2)$，空间复杂度：$O(n)$
  

最大乘积数组

• 最大乘积数组
• 题目大意：给定一个整数数组，可能包含正、负、零。求的一个子数组，这个子数组的各个元素乘积是最大的。子数组表示数组中元素是连续的。

思路1

• 暴力寻找
• 与最大子数组的和类似，我们可以枚举所有子数组的长度，获取每个长度下数组的乘积。找出最大的一个。

思路2

• 分析子数组的构成情况，假设我们已经得到一个到$a_i$结尾的最大乘积数组，那么以$a_{i+1}$结尾的子数组的乘积如何构成呢？
• 由于数组元素可能由正也有负数，那么如果$a_{i+1}$ 是负数，那么与它乘积一起构成的最大子数组就需要时负数才行，负数乘以负数才能得到正数，才可能最大。由此看来，我们还需要知道以$a_i$结尾的最小子数组才能构成。最大的乘积子数组。
• 所以我们假设两个数组，一个是$maxarr[0,n),minarr[0,n)$，分别表示以$a_i$结尾的元素的乘积的最大、最小值。
• 假设$dp[i]$是以$a_i$结尾的子数组的最大乘积。

$$dp[i] = \left\{\begin{matrix} maxarr[i-1]* a_i & a_i \gt 0 \\ minarr[i-1]* a_i & a_i \lt 0 \end{matrix}\right.\\ maxarr[i] = \left\{\begin{matrix} minarr[i-1]* a_i & a_i \lt 0 \\ maxarr[i-1]* a_i & a_i \gt 0 \end{matrix}\right.\\ minarr[i] = \left\{\begin{matrix} minarr[i-1]* a_i & a_i \gt 0 \\ maxarr[i-1]* a_i & a_i \lt 0 \end{matrix}\right.\\ $$

int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n,vector<int>());
        if( n <=0 ) 
            return 0;
        for(int i = 0; i < n; i++ ) {
            dp[i] = {nums[i],nums[i]};
        }
        int maxv = nums[0];
        for(int i = 1; i < n; i++ ) {
            int a = nums[i];
            if( a < 0) {
                dp[i][0] = max(dp[i-1][1] * a ,a);
                dp[i][1] = min(dp[i-1][0] * a, a);
            }else if( a > 0) {
                dp[i][0] = max(dp[i-1][0] * a, a);
                dp[i][1] = min(dp[i-1][1] * a, a);
            }
            maxv = max(maxv,dp[i][0]);
        }
        return maxv;
}

• 时间复杂度:$O(n)$ ，空间复杂度:$O(n)$
• 每次只需要和前一个状态的数据$minar[i],maxarr[i]$有关系，可以优化这两个空间。