动态规划

动态规划

解题框架：

1.定义子问题

原问题要能用子问题表示
一个子问题的解要能通过其他子问题的解求出。比如f(k)可以用f(k-1)和f(k-2)表示

2.写出子问题的递推关系
写base case
大部分是0和1的状态
确定选和不选的过程
选的话就是当前结点的值+dp[k-1]
不选的话问题就变成dp[k-1]
最简单的一种
看当前子问题和前一个子问题之间的关系
一维
f(i)和f(i-1)
二维
f(i,j)和f(i-1,j)和f(i,j-1)
3.确定 DP 数组的计算顺序（绝大多数是用DP数组循环）
4.空间优化（可选）
5.变形
在「定义子问题」的步骤，有的题目需要定义二维、三维的子问题。
在「子问题递推关系」的步骤，有的题目需要分情况讨论，有复杂的 max、min、sum 表达式。
在「DP 数组计算顺序」的步骤，有的题目需要反向计算，甚至斜向计算。
在「空间优化」的步骤，有的题目需要使用临时变量，使用特殊的计算顺序。

例题（Easy）

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

思路分析

定义子问题：前面的大于零，一直加下去（选），前面的小于零，从当前位置重新开始（不选）
递推关系：dp [i] = dp[i-1]+nums[i] (选) dp[i] = nums[i] （不选）

base case ：dp[0] = nums[0]

class Solution {
  public int maxSubArray(int[] nums) {
      int res = nums[0];
      int n = nums.length;
      int [] dp = new int[n];
      //base case
      dp[0] = nums[0];
      for(int i = 1;i<n;i++){   //为什么不等于n？ 索引到n-1
          if(dp[i-1]>0){
              dp[i] = nums[i]+ dp[i-1];
          }else{
              dp[i] = nums[i];
          }
          res = Math.max(dp[i],res);
      }
      return res;
  }
}

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路分析

出现重叠子问题也就可以用动态规划来解决
创建大小N的数组需要用0到N-1的索引去访问，否则会越界
```
class Solution {
  public int climbStairs(int n) {
      int [] dp = new int[n+2]; 
     // dp[0] = 0;
   //  dp[0] = 1;  //dp 0 代表的是么有意义的
      dp[1] = 1;   
      dp[2] = 2;     //这数组会越界，把原来的n+1扩容到n+2
      for(int i=3;i<=n;i++){  
          dp[i] = dp[i-1] + dp[i-2];
      }
      return dp[n];
  }
}
```
121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路分析

重叠子问题就是每一天都要进行类似的判断
难点在于推导状态转移方程：(这里有约束条件，需要单独开一维数组)

dp[i][j] ：在这里i表示当前的天，j表示是否持股的状态（0代表不持股）也就是说最后的输出是到了最后一天：应该是dp[len - 1][0]

推导状态转移方程：
dp[i][0]：表示今天不持股，可能有两种情况：dp[i][0] = max (dp [i-1] [0] , dp[i-1][1] + prices[i])
- 昨天不持股，今天没有任何操作
- 昨天持股，今天卖出，卖出操作加上prices[i]

dp[i][1]：表示今天持股，也有两种情况：dp[i][1] = max (dp [i-1] [1] , - prices[i])

昨天不持股，今天买入，买入操作减去prices[i]
昨天持股，今天没有操作 ```java public class Solution {

public int maxProfit(int[] prices) { int len = prices.length; // 特殊判断 if (len < 2) {
```
   return 0;
```
} int[][] dp = new int[len][2];

// dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数 // dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数

// 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价 dp[0][0] = 0; dp[0][1] = -prices[0];

// 从第 2 天开始遍历 for (int i = 1; i < len; i++) {
```
   dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
   dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
```
} return dp[len - 1][0]; } }

作者：liweiwei1419 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/bao-li-mei-ju-dong-tai-gui-hua-chai-fen-si-xiang-b/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

<a name="GUN1a"></a>
### [338. 比特位计数](https://leetcode.cn/problems/counting-bits/)
> 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
<a name="oyVBp"></a>
#### 思路分析
[https://leetcode.cn/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/](https://leetcode.cn/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/)<br />对于所有数字，只有奇数和偶数，涉及到二进制有如下的规律：
- 对于奇数，二进制表示中，奇数一定比前面那个偶数多一个1（多的是最低位的1）
例如：0 = 0 ，1 = 1，2 = 10，3 = 11 。。。
- 对于偶数，二进制表示中，偶数中1的个数和除以2之后的数中的1的个数一样多，
例如：2 = 10 3 = 11，4 = 100，8 = 1000 
```java
class Solution {
    public int[] countBits(int n) {
        int [] res = new int [n+1];
        res[0] = 0;
        for(int i=1;i<=n;i++){
            if(i % 2 == 1){   //奇数
                res[i] = res[i-1] +1;
            }
            else{
                res[i] = res[i/2];
            }
        }
        return res;
    }
}

例题（Mid）

309. 最佳买卖股票时机含冷冻期

给定一个整数数组prices，其中第 _prices[i] 表示第 _i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路分析

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int [][] dp = new int [n][3];
        if(n < 2){
            return 0;
        }
        dp[0][0] = 0;
        dp[0][1] =  -prices[0];
        dp[0][2] = 0;
        for(int i = 1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
            dp[i][1] = Math.max(dp[i-1][0] - prices[i],dp[i-1][1]);
            dp[i][2] = dp[i-1][1] + prices[i];
        }
        return Math.max(dp[n-1][0],dp[n-1][2]);
    }
}

第一步：状态定义：dp[node][j] ：这里 node 表示一个结点，以 node 为根结点的树，并且规定了 node 是否偷取能够获得的最大价值。

j = 0 表示 node 结点不偷取；
j = 1 表示 node 结点偷取。

LeetCode Hot 100

动态规划

解题框架：

例题（Easy）

53. 最大子数组和

思路分析

70. 爬楼梯

思路分析

121. 买卖股票的最佳时机

思路分析

例题（Mid）

309. 最佳买卖股票时机含冷冻期

思路分析