秋招突击——6/22——复习{区间DP——加分二叉树，背包问题——买书}——新作{移除元素、实现strStr（）}

引言

• 今天做了一个噩梦，然后流了一身汗，然后没起来，九点多才起床背书。十点钟才开始把昨天那道题题目过一遍，然后十一点才开始复习题目，为了不耽误下午的时间，所以这里的就单纯做已经做过的题目，主打一个有量，不在学习新的dp。

复习

区间DP——加分二叉树

• 这道题差不多看了第二遍，第一次学的时候就蛮难的，不过有固定的编程范式，不过这里没想起来。提供一下之前的分析思路。

  • 第一次分析
  • 区间DP——合并石子

• 之前做了两次，这次看看能不能一次过。

个人实现

• 区间DP集合表示是f[i][j],
  • i是区间的左端点
  • j是区间的右端点，
• 集合划分是区间的中间的，所以需要遍历枚举区间[i,j]中所有的区间分割点
• 具体的代码流程如下
  • 列举区间长度
  • 列举区间左端点
  • 枚举的区间的分割点

实现问题

• 区间长度的上下限有没有特殊情况，需不需要特殊考虑？如果区间长度为1，或者为n怎么办？
• 特殊情况1
  • 区间长度为1，表示的左右子节是重合的，所以需要特殊考虑，当前情况是叶子节点
  • 区间长度就是1到n，不用考虑n+1，之前那个题目使用n+1是特殊情况，实际情况下，不需要使用使用n+1，而且这道题使用n+1也没有任何意义，那道题股票买卖题n+1一天的某种情况，是之前最大的。

#include <iostream>

using namespace std;

const int N = 35;
int f[N][N],n,rp[N][N];  // f表示区间的状态记录，r表示根节点的记录状态
int s[N];

void dfs(int l,int r){
   
    if (l > r)  return ;
    int k = rp[l][r];
    cout<<k<<" ";
    if (k - 1 >= l) dfs(l,k - 1);
    if (k + 1 <= r) dfs(k + 1,r);
}

int main(){
   
    cin>>n;
    for (int i = 1; i <= n; ++i) {
   
        cin>>s[i];
        s[i] += s[i - 1];
    }
    
    // 区间DP
    for (int len = 1; len <= n; ++len) {
   
        // 列举区间左端点
        for (int l = 1; l + len <= n; ++l) {
   
            // 计算区间的右端点
            int r = l + len  - 1;
            // 列举区间的分割点
            for (int k = l; k <= r; ++k) {
   
            	if（看== 1）
                int temp;
                if (k == l){
   
                    // 左端点为空
                    temp = (s[k] -s[k - 1]) + f[k + 1][r];
                }else if(k == r){
   
                    // 右子树为空
                    temp = (s[k] -s[k - 1]) + f[l][k - 1];
                }else{
   
                    // 左右子树都不为空
                    temp = (s[k] -s[k - 1]) +</