########################################
动态规划
########################################

动态规划我也没什么好的办法，刷题找感觉吧

小青蛙跳台阶
****************************************

选自《剑指 Offer》的一道题，leetcode 的答案感觉有点问题，而且牛客上的题解更清晰，所以就选用牛客的。下面的内容摘自牛客题解：

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

题解

| 此题和斐波拉契数列做法一样。也将用三个方法来解决，从入门到会做。
| 考察知识：递归，记忆化搜索，动态规划和动态规划的空间优化。
| 难度：一星

方法一：递归
========================================

题目分析，假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n-1个台阶，一种是走到第n-2个台阶。所以f[n] = f[n-1] + f[n-2].

| 那么初始条件了，f[0] = f[1] = 1。
| 所以就变成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1，目标求f[n]

看到公式很亲切，代码秒秒钟写完。

.. code-block:: cpp

   int Fibonacci(int n) {
      if (n<=1) return 1;
      return Fibonacci(n-1) + Fibonacci(n-2);
   }

| 优点，代码简单好写，缺点：慢，会超时
| 时间复杂度：O(2^n)
| 空间复杂度：递归栈的空间

方法二：记忆化搜索
========================================

拿求f[5] 举例

.. image:: assets/2021-08-29-01-07-18.png

| 通过图会发现，方法一中，存在很多重复计算，因为为了改进，就把计算过的保存下来。
| 那么用什么保存呢？一般会想到map， 但是此处不用牛刀，此处用数组就好了。

.. code-block:: cpp

   int Fib(int n, vector<int>& dp) {
      if (n<=1) return 1;
      if (dp[n] != -1) return dp[n];
      return dp[n] = Fib(n-1) + Fib(n-2);
   }
   int Fibonacci(int n) {
      vector<int> dp(45, -1); // 因为答案都是>=0 的， 所以初始为-1，表示没计算过
      return Fib(n, dp);
   }

| 时间复杂度：O（n）， 没有重复的计算
| 空间复杂度：O（n）和递归栈的空间

方法三：动态规划
========================================

| 虽然方法二可以解决此题了，但是如果想让空间继续优化，那就用动态规划，优化掉递归栈空间。
| 方法二是从上往下递归的然后再从下往上回溯的，最后回溯的时候来合并子树从而求得答案。
| 那么动态规划不同的是，不用递归的过程，直接从子树求得答案。过程是从下往上。

.. code-block:: cpp

   int Fibonacci(int n) {
      vector<int> dp(n+1, 0);
      dp[0] = dp[1] = 1;
      for (int i=2; i<=n; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
      }
      return dp[n];
   }

| 时间复杂度：O(n)
| 空间复杂度：O(n)

最终成果
========================================

| 发现计算f[5]的时候只用到了f[4]和f[3], 没有用到f[2]...f[0],所以保存f[2]..f[0]是浪费了空间。
| 只需要用3个变量即可。

.. code-block:: cpp

   int Fibonacci(int n) {
      if (n == 0 || n == 1) return n;
      int a = 1, b = 1, c;
      for (int i=2; i<=n; ++i) {
            c = a + b;
            a = b;
            b = c;
      }
      return c;
   }


| 时间复杂度：O（n）
| 空间复杂度：O（1）

完美！

最大子数组问题
****************************************

问题描述：

   给定一个数组arr，返回子数组的最大累加和
   例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
   题目保证没有全为负数的数据
   [要求]
   时间复杂度为O(n)，空间复杂度为O(1)

题解： [#maxsubarr]_

解法一：暴力解
思路步骤：

   - 常规思路，直接两层for循环暴力枚举
   - 找到符合题意的最大累加和
   - 虽然理论上可行，但是时间复杂度为O(N^2)，实际运行是无法AC的。仅仅作为一种学习思路。

C++ 参考代码：(超时)

.. code-block:: cpp

   class Solution {
   public:
      /**
      * max sum of the subarray
      * @param arr int整型vector the array
      * @return int整型
      */
      int maxsumofSubarray(vector<int>& arr) {
         // write code here
            int result = INT32_MIN;
         int count = 0;
         for (int i = 0; i < arr.size(); i++) { // 设置起始位置
               count = 0;
               for (int j = i; j < arr.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
                  count += arr[j];
                  result = count > result ? count : result;
               }
         }
         return result;

      }
   };

复杂度分析：

   时间复杂度：O(N^2) N为数组长度，俩层循环，，根据大O一般法则可知复杂度O(N^2)

   空间复杂度：O(1) 常数空间

解法二：贪心

思路步骤：

#. 怎么贪？
#. 不妨以case:[1, -2, 3, 5, -2, 6, -1]为例
#. 当遇到-2时，累加和反而变为负数，此种情况不可能成为最大和
#. 因此在遇到负数时，因该重置累加和为0，继续从i+1开始计算
#. 最后得到一个局部最大和
#. 最终得到一个全局最大和，即是答案

C++ 参考代码：

.. code-block:: cpp

   class Solution {
   public:
      /**
      * max sum of the subarray
      * @param arr int整型vector the array
      * @return int整型
      */
      int maxsumofSubarray(vector<int>& arr) {
         // write code here
         int result = INT_MIN;
         int sum = 0;
         for(int i =0; i < arr.size(); ++i){
               sum += arr[i];
               if(sum>result) result = sum;
               if(sum<0) sum = 0;

         }
         return result;
      }
   };

复杂度分析：

   - 时间复杂度：O(N) N为数组长度，取决于for循环。
   - 空间复杂度：O(1) 常数空间开销


解法三：分治思想

思路步骤：

我们的最大序列和可能会分别在前半部分和后半部分与中间部分出现。

关于前两种情况，如果只出现在前后半部分，可以递归求解得到。第三种情况：跨越输入数据的中部而位于左右俩部分之中，可以通过求出前半部分（包含该部分最后一个元素）的最大和以及后半部分（包含该部分第一个元素）的最大和得到，二者相加即可。

   #. 将目标数组一分为二：左右两部分
   #. 递归求解
   #. 计算前半部分最大和
   #. 计算后半部分最大和
   #. 计算最终全局最大和
   #. return 答案

.. code-block:: java

   import java.util.*;


   public class Solution {
      /**
      * max sum of the subarray
      * @param arr int整型一维数组 the array
      * @return int整型
      */
         public int maxSum(int[] a,int left,int right){
         if(left==right){
               return a[left];
         }
         int center = (left+right)/2;
         //计算前半部分最大和
         int maxLeftSum = maxSum(a,left,center);
         //计算后半部分最大和
         int maxRightSum = maxSum(a,center+1,right);

         //计算分界部分(前半部分)
         int maxLeftBorderfeSum = Integer.MIN_VALUE,leftBorderSum = 0;
         for(int i=center;i>=left;i--){
               leftBorderSum+=a[i];
               if(leftBorderSum>maxLeftBorderfeSum){
                  maxLeftBorderfeSum = leftBorderSum;
               }
         }
         //计算分界部分(前半部分)
         int maxRightBorderSum =Integer.MIN_VALUE,rightBorderSum=0;
         for(int i=center+1;i<=right;i++){
               rightBorderSum+=a[i];
               if(rightBorderSum>maxRightBorderSum){
                  maxRightBorderSum = rightBorderSum;
               }
         }
         //取全局最优
      return max3(maxLeftSum,maxRightSum,maxRightBorderSum+maxLeftBorderfeSum);
      }
      /*计算三值最大*/
      public int max3(int a,int b,int c){
         return Math.max(Math.max(a,b),c);
      }


      public int maxsumofSubarray (int[] arr) {
         // 调用
         return maxSum(arr,0,arr.length-1);

      }
   }

复杂度分析：

   - 时间复杂度：O(NlogN)，常数量+两层循环O(N)+递归部分的开销O(N/2),为了简化计算，这里不再给出精确的求解。2T(N/2)+O(N)且T(1)=1,显然可以得到T(2) = 4 = 22,T(4) = 12 = 4*3,显式的可以得到，若2k2^k2k 则O(N) = N(K+1) = NlogN+N = NlogN，所以最终时间复杂度：O(NlogN)
   - 空间复杂度：O(1)，常数空间开销。


.. [#maxsubarr] `数组的最大累加和问题 <https://blog.nowcoder.net/n/924017844ea14342ba7536ddff8b213f>`_

买卖股票的最好时机
****************************************

描述

   假设你有一个数组，其中第 i个元素是股票在第 i 天的价格。
   你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。

暴力解法： [#goodtime]_


.. code-block:: cpp

   class Solution {
   public:
      /**
      *
      * @param prices int整型vector
      * @return int整型
      */
      int maxProfit(vector<int>& prices) {
         // write code here
         int result = 0;
         int tmp;
         for(int i =0; i < prices.size() - 1; ++i){
               for( int j = i+1; j < prices.size(); ++j ){
                  tmp = prices[j] - prices[i];
                  if(tmp > result) result = tmp;
               }
         }
         return result;
      }
   };

时间复杂度是 O(n^2) 空间复杂度是 O(1)

另一种思路先预处理成差值，然后使用最大子数组的形式求解：

.. code-block:: cpp


   class Solution {
   public:
      /**
      *
      * @param prices int整型vector
      * @return int整型
      */
      int maxProfit(vector<int>& prices) {
         // write code here
         int *profiles = new int[prices.size() - 1];
         // 计算差
         for(int i = 0; i < prices.size() - 1; ++i){
               profiles[i] = prices[i+1] - prices[i];
         }
         // 计算最大子数组
         int result = INT_MIN;
         int tmp = 0;
         for(int i = 0; i < prices.size() - 1; ++i){
               tmp += profiles[i];
               if(tmp > result) result = tmp;
               if(tmp < 0 ) tmp = 0;
         }
         return result < 0 ? 0 : result;
      }
   };

算法的时间复杂度是 O(2n) 空间复杂度是 O(n)

.. [#goodtime] `买卖股票的最好时机 <https://blog.nowcoder.net/n/b0de6a3299d94fd8b50ccf976232c162>`_

338. 比特位计数
****************************************

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。 [#bitcount]_

进阶：

    很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
    你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

如果 i 是偶数，则 i == i/2 << 1，末尾 +0
如果 i 是奇数，则 i == i/2 <<1 + 1，末尾 +1

.. code-block:: cpp

   class Solution {
   public:
      vector<int> countBits(int n) {
         vector<int> res(n+1, 0);
         for(int i = 0; i <=n; ++i){
               if(i%2==0) res[i] = res[i/2];
               else res[i] = res[i/2]+1;
         }
         return res;
      }
   };

.. [#bitcount] `比特位计数 <https://leetcode-cn.com/problems/counting-bits>`_