Nginx Proxy Manager (NPM) 是方便的可视化管理 Nginx 代理的工具，同时支持 Let's Encrypt 的 SSL 的申请和自动续申，是非常方便的工具

我是用宝塔面板部署 Web（Vue3项目，就是普通 Web 项目） 和后端 (一些需要反向代理的链接，使用 `/api` 路径反向代理到其他服务器，我部署的是后端服务)以及一些 Docker 项目 (博客，内部使用了 Caddy 服务器，也是自动申请和续申 SSL 证书)

## 1. 安装 NPM

首先，我考虑到我管理 Web 项目都是使用宝塔 (就是使用宝塔创建 PHP 静态项目，其实就是纯 Web 项目，然后他会在 `/www/wwwroot` 下创建文件夹)，于是，如果需要无痛过渡宝塔内置 Nignx 到 NPM 的话就需要加入 dockerfile 中的文件夹映射 `/www/wwroot:/www/wwroot`

于是根据 NPM 官网的示例 docker-compose. yml 简单修改就得到了下面的配置文件

```yml
version: '3.8'
services:
  nginxmgr:
    image: 'jc21/nginx-proxy-manager:latest'
    restart: unless-stopped
    ports:
	  # HTTP 网站的端口
      - '80:80'
      # NPM管理后台的端口
      - '81:81'
      # HTTPS 网站的端口
      - '443:443'
    volumes:
      - /data:/data
      - /letsencrypt:/etc/letsencrypt
      # 需要映射一个静态资源路径，如果无特殊要求，直接在/data路径下放置静态Web资源即可
      - /www/wwwroot:/www/wwwroot
```

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/22c642e6ec658d00a60555ded66883c9.png)

根据模板文件创建编排项目即可

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/0c53d079ced04cb68bf86e3863234c27.png)

使用 `ip+81` 访问 NPM 后台管理平台

首次登录用户名和密码为，需要修改用户名和密码，根据提示修改即可

```
Email:    admin@example.com
Password: changeme
```

## 2. 配置 Web 前端项目

点击 Hosts 创建反代配置

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/8fa5f644947941eae2a9e8fbe0b6d3fd.png)

输入域名和本地端口，如果是使用 nginx 代理的话，IP 为本地 IP 和端口为80

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/014ad7f9db399eea71032e6b7dbab30e.png)

对于我的 Web 项目，它的文件路径在 `www/wwroot` 下

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/31d5b1dd0739cda7724e597636b39211.png)

Nginx 配置文件为

```config
server {
        listen 80;
        server_name 项目域名;
        location / {
            root   /www/wwwroot/项目路径/;
            try_files $uri $uri/ /index.html;
            index  index.html index.htm;
        }

       #gzip
       #开启gzip功能
       gzip on;
       ... 省略
       
       # 反向代理后端域名到 前端
        location /api/ {
           proxy_pass http://后端域名:8081;
           proxy_set_header Host $host;
           proxy_set_header X-Real-IP $remote_addr;
           proxy_set_header REMOTE-HOST $remote_addr;
           proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
           
          # rewrite ^/api/(.*)$ /$1 break;
       }
    }
```

但是我们不能直接将这个配置文件放入 NPM 的配置文件中，我们可以在高级选项卡中添加自定义 Nginx 配置

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/e7418fd171d8c942e07fdbbe1df83fa7.png)

对于我的 Web 项目，把下面内容粘贴到文本框中即可

```config
location / {
	root   /www/wwwroot/项目路径/;
	try_files $uri $uri/ /index.html;
	index  index.html index.htm;
}

#gzip
#开启gzip功能
gzip on;
... 省略

# 反向代理后端域名到 前端
location /api/ {
   proxy_pass http://后端域名:8081;
   proxy_set_header Host $host;
   proxy_set_header X-Real-IP $remote_addr;
   proxy_set_header REMOTE-HOST $remote_addr;
   proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
   
  # rewrite ^/api/(.*)$ /$1 break;
}
```

这样就完成了 NPM 对于 Web 项目的配置，在 `data/nginx` 下可看见我们的 Nginx 配置文件

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/db16fb3cb8f0bf1962b29cb9a968050e.png)
配置文件列表

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/09abb5cf1ec55e1111df8e69cf22456a.png)

配置文件内容

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/77949135e52bee5aa434c0cfded85448.png)


## 3. 配置自动申请 SSL 证书

我们讲到 Let's Encrypt 可以免费申请 SSL 证书，它只需要一共邮箱和一个可以访问通的域名即可申请，但是申请证书有效期为90天，90天后需要重新申请，像 Caddy 等一些服务器可以自带 Let's Encrypt SSL 证书的申请和续申，但是 Nginx 肯定是不行的，于是可以使用 NPM 进行申请

NPM 申请也很简单，可以在创建反代配置时配置

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/e83229089c9339873075caf1e7428671.png)

也可以在单独的 SSL 管理页进行申请

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/9fadab4993daa9d4458a83d6aabd5fbc.png)

申请过程请确保网站是可访问的，并且 Let's Encrypt 访问并不一定很通畅，有时候可能需要多次尝试才能成功 (尤其是国内服务器)

## 4. 普通反向代理

我使用 vanblog 作为博客网站框架，其中使用了 Caddy 作为服务器并自动申请 SSL 证书，但是我不需要使用 Caddy 作为服务器，我需要使用 Nginx 独立管理我的博客，于是我使用 NPM 反代 vanblog 的 HTTP 端口 (我设置的为8089，不能使用80和443端口)

于是配置为

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/d68c88d2214f434a60ce3389d7f1e3e8.png)

同样可配置 SSL 证书

## 5. 配置默认未找到页面

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/25b9238a1a925a1bdbd0ac3cd95f270e.png)

简单使用Nginx Proxy Manager

最近使用某个时间统计软件，需要在多个设配上使用，但是它没有数据同步功能，于是我使用 gitee 进行数据同步，需要使用下面几个命令

上传到 gitee
```bash
git add .
git commit -m "2024 5-14 Add Time"
git push --set-upstream gitee master --force
```

重置本地分支为 gitee 的数据

```bash
git fetch --all
git reset --hard gitee/master
```

于是我想到使用 Git 自定义命令，并且自己配置提交信息，如配置提交时间

```bash
date \"+%Y %m-%d %H:%M:%S\"
```

如何配置 Git 自定义命令
1. 打开用户目录，找到 `.gitconfig` 文件
2. 添加 `[alias]`

```ini
[alias]
  tai-sync = "!f() { current_date=$(sh -c 'date \"+%Y %m-%d %H:%M:%S\"'); git add .; git commit -m \"$current_date Add Time\"; git push --set-upstream \"$1\" master --force; }; f"
  tai-get = "!git fetch --all && git reset --hard \"$1\"/master"
```

这样使用 `git tai-sync gitee` 和 `git tai-get gitee` 即可完成上面的五条命令

使用Git自定义命令

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/b575df149fe6f956568067d103ae8d06.png)

### 1. Spring Bean
#### 1.1 单例 Bean 是线程安全的吗

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/b79f096c7eca70e0b3586d37d2ae09e9.png)
- singleton : bean 在每个 Spring IOC 容器中只有一个实例。
- prototype：一个 bean 的定义可以有多个实例。 

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/ed1e7314323c272c26701e59b3957fe6.png)
Spring bean 并没有可变的状态 (比如 Service 类和 DAO 类)，所以在某种程度上说 Spring 的单例 bean 是线程安全的。

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/09899a8f8cdc6e58ed0c75c212b3115d.png)
#### 1.2 Bean 的生命周期

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/05e679509b95c7ba8a9cec10f08e82df.png)

1. 定义Bean

>Spring 容器在进行实例化时，会将 xml 配置的 `<bean>` 的信息封装成一个 `BeanDefinition` 对象，Spring 根据 `BeanDefinition` 来创建 Bean 对象，里面有很多的属性用来描述 Bean

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/379ff41952e7eb71c68c56692bb21430.png)
2. 初始化赋值和销毁Bean

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/997108a99035c24d566ed4bbb8add11d.png)

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/c30c9b3813d3534977c34b33ec5dc195.png)
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/17e65d3d2a814262b33dae176aaa788e.png)

#### 1.3 Bean 的循环依赖

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/b57f007153522beb7346a87faad748cc.png)

**三级缓存解决循环依赖**
- Spring 解决循环依赖是通过三级缓存，对应的三级缓存如下所示：

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/94a441e6f9689bac8d1aeb4441cec7cf.png)

**一级缓存作用**：限制 bean 在 beanFactory 中只存一份，即实现 singleton scope，解决不了循环依赖
**二级缓存**：缓存早期的 bean 对象（生命周期还没走完），二级缓存不能解决对象增强问题
**三级缓存**：缓存的是 ObjectFactory，表示对象工厂，用来创建某个对象的

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/c6f8748095a580d9850f04e8d0ebbd3f.png)
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/fece722b2def51b854a2e44be1eb0e09.png)

### 2. Spring AOP

AOP 称为面向切面编程，用于将那些与业务无关，但却对多个对象产生影响的公共行为和逻辑，抽取并封装为一个可重用的模块，这个模块被命名为“切面”（Aspect），减少系统中的重复代码，降低了模块间的耦合度，同时提高了系统的可维护性。

常见的 AOP 使用场景：
- 记录操作日志
- 缓存处理
- Spring 中内置的事务处理

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/9d269639da45221bb707a62493d96eba.png)

#### 2.1 记录日志

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/2cac42ab757755c2a5b9d734801d22ae.png)

获取请求的用户名、请求方式、访问地址、模块名称、登录 ip、操作时间，记录到数据库的日志表中

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/6d83e0f7b2654af0f39bbc2b1d94d41a.png)

#### 2.2 事务

Spring 支持**编程式事务管理**和**声明式事务管理**两种方式。
- **编程式事务控制**：需使用 TransactionTemplate 来进行实现，对业务代码有侵入性，项目中很少使用
- **声明式事务管理**：声明式事务管理建立在 AOP 之上的。其本质是通过 AOP 功能，对方法前后进行拦截，将事务处理的功能编织到拦截的方法中，也就是在目标方法开始之前加入一个事务，在执行完目标方法之后根据执行情况提交或者回滚事务。

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/13ddf5a32ae6100a723f5aa1d1518714.png)

### 3. 事务失效

Spring 事务失效的场景有哪些
- 异常捕获处理
- 抛出检查异常
- 非 public 方法

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/82656ad1ede4f3c2d15365890f5b4a47.png)

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/1bf269ef9c67e2a15c34699694d69946.png)

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/b8d0f3d06e724bed37d26491151f3b82.png)

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/4a09e2579dee9852f8a81c83768afa65.png)

### 4. SpringMVC

1. 视图阶段（老旧 JSP 等）
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/e6df9cea1fd0708522f3c96a8b4d8dc0.png)
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/9579a9fe68523abda357ec9ad00561c9.png)


2. 前后端分离阶段（接口开发，异步）
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/f285a263a406275feab6afaa80203270.png)
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/c7631c1a8d222b1013f3d52f7c996b94.png)

### 5. SpringBoot 自动配置原理

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/fb1cca13d3a0f257deccbc8e5d1168a2.png)

点击进入 `@SpringBootApplication` 注解，可看见其由几个注解组成
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/0665d0e8f50e6bbe75c0910f8524e087.png)
- `@SpringBootConfiguration` ：该注解与 `@Configuration` 注解作用相同，用来声明当前也是一个配置类。
- `@ComponentScan` ：组件扫描，默认扫描当前引导类所在包及其子包。
- `@EnableAutoConfiguration` ：SpringBoot 实现自动化配置的核心注解。

其中 `@EnableAutoConfiguration` 又由几个注解组成
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/5034b9b7c45ac9a72a325456fbfd2078.png)

点开 `spring.factories` 中其中一个 configuration，可看见

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/db6bc82a4e5ae8f9ef28723ec1a25301.png)

### 6. Spring 框架中常见的注解

**Spring 的常见注解有哪些？**

| 注解                                          | 说明                                  |
| ------------------------------------------- | ----------------------------------- |
| @Component、@Controller、@Service、@Repository | 使用在类上用于实例化Bean                      |
| @Autowired                                  | 使用在字段上用于根据类型依赖注入                    |
| @Qualifier                                  | 结合@Autowired一起使用用于根据名称进行依赖注入        |
| @Scope                                      | 标注Bean的作用范围                         |
| @Configuration                              | 指定当前类是一个 Spring 配置类，当创建容器时会从该类上加载注解 |
| @ComponentScan                              | 用于指定 Spring   在初始化容器时要扫描的包          |
| @Bean                                       | 使用在方法上，标注将该方法的返回值存储到Spring容器中       |
| @Import                                     | 使用@Import导入的类会被Spring加载到IOC容器中      |
| @Aspect、@Before、@After、@Around、@Pointcut    | 用于切面编程（AOP）                         |
**SpringMVC 常见的注解有哪些？**

| 注解              | 说明                                               |
| --------------- | ------------------------------------------------ |
| @RequestMapping | 用于映射请求路径，可以定义在类上和方法上。用于类上，则表示类中的所有的方法都是以该地址作为父路径 |
| @RequestBody    | 注解实现接收http请求的json数据，将json转换为java对象               |
| @RequestParam   | 指定请求参数的名称                                        |
| @PathViriable   | 从请求路径下中获取请求参数(/user/{id})，传递给方法的形式参数             |
| @ResponseBody   | 注解实现将controller方法返回对象转化为json对象响应给客户端             |
| @RequestHeader  | 获取指定的请求头数据                                       |
| @RestController | @Controller + @ResponseBody                      |
**Springboot 常见注解有哪些？**

| 注解                       | 说明                              |
| ------------------------ | ------------------------------- |
| @SpringBootConfiguration | 组合了- @Configuration注解，实现配置文件的功能 |
| @EnableAutoConfiguration | 打开自动配置的功能，也可以关闭某个自动配置的选         |
| @ComponentScan           | Spring组件扫描                      |

| 注解                                          | 说明                                  |
| ------------------------------------------- | ----------------------------------- |
| @Component、@Controller、@Service、@Repository | 使用在类上用于实例化Bean                      |
| @Autowired                                  | 使用在字段上用于根据类型依赖注入                    |
| @Qualifier                                  | 结合@Autowired一起使用用于根据名称进行依赖注入        |
| @Scope                                      | 标注Bean的作用范围                         |
| @Configuration                              | 指定当前类是一个 Spring 配置类，当创建容器时会从该类上加载注解 |
| @ComponentScan                              | 用于指定 Spring   在初始化容器时要扫描的包          |
| @Bean                                       | 使用在方法上，标注将该方法的返回值存储到Spring容器中       |
| @Import                                     | 使用@Import导入的类会被Spring加载到IOC容器中      |
| @Aspect、@Before、@After、@Around、@Pointcut    | 用于切面编程（AOP）                         |

| 注解              | 说明                                               |
| --------------- | ------------------------------------------------ |
| @RequestMapping | 用于映射请求路径，可以定义在类上和方法上。用于类上，则表示类中的所有的方法都是以该地址作为父路径 |
| @RequestBody    | 注解实现接收http请求的json数据，将json转换为java对象               |
| @RequestParam   | 指定请求参数的名称                                        |
| @PathViriable   | 从请求路径下中获取请求参数(/user/{id})，传递给方法的形式参数             |
| @ResponseBody   | 注解实现将controller方法返回对象转化为json对象响应给客户端             |
| @RequestHeader  | 获取指定的请求头数据                                       |
| @RestController | @Controller + @ResponseBody                      |

Spring框架面试题

MySQL面试题

## 198. 打家劫舍

#动态规划

[198. 打家劫舍 - 力扣（LeetCode）](https://leetcode.cn/problems/house-robber/description/)

**思路分析**
- 题目要求不能连着偷，那么在递归中可以考虑各种路线中，在当前 i 位置时是去前-1个值更好，还是取前-2个值加当前 i 值更好
- 写出状态转移方程
$$
dfs[i] = max(dfs(i-1), dfs(i-2) + nums[i])
$$
我们可以将选的过程画成一颗二叉树，如下，其中0-4表示的是 i 的值，选与不选表示的是是否选择4这个节点
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/5279e71cf972cf1046a573a62548fa39.png)

代码如下
```java
import java.util.*;

class Solution {
    private int[] nums;

    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        return dfs(n - 1);
    }

    /**
     * 递归遍历房子
     * 
     * @param i
     * @return
     */
    private int dfs(int i) {
        // 如果i<0表示没有房子可选了，直接返回0
        if (i < 0) {
            return 0;
        }
        // 使用状态转移方程表示获取的最大值
        /*
         * dfs(i-1)表示在当前位置i不选，因为 “如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。”
         * dfs(i - 2) + nums[i] 表示在当前位置i选
         * 使用max则可选出这两种操作哪种得到的值最大
         */
        int res = Math.max(dfs(i - 1), dfs(i - 2) + this.nums[i]);
        return res;
    }
}
```

显然，答案**超时**了，我们需要优化代码，我们注意到搜索树，它有一些重复的地方，我们可以进行**剪枝**操作

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/ac20489dc0542d4b7090951cef908ead.png)

**优化一**
- 我们使用一个 memo 数组记录每次计算的值，然后在递归中判断是否进行过计算，如果 memo 数组中有值，则直接返回

```java
import java.util.*;

class Solution {
    private int[] nums;
    private int[] memo;

    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        this.memo = new int[n];
        Arrays.fill(this.memo, -1);
        return dfs(n - 1);
    }

    /**
     * 递归遍历房子
     * 
     * @param i
     * @return
     */
    private int dfs(int i) {
        // 如果i<0表示没有房子可选了，直接返回0
        if (i < 0) {
            return 0;
        }
        // 如果当前值计算过了，那么直接返回
        if (this.memo[i] != -1) {
            return this.memo[i];
        }
        // 使用状态转移方程表示获取的最大值
        /*
         * dfs(i-1)表示在当前位置i不选，因为 “如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。”
         * dfs(i - 2) + nums[i] 表示在当前位置i选
         * 使用max则可选出这两种操作哪种得到的值最大
         */
        int res = Math.max(dfs(i - 1), dfs(i - 2) + this.nums[i]);
        this.memo[i] = res;
        return res;
    }
}
```

这样算法的复杂度就优化到了 $O(n)$

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/e0b7689c5e7f93119bdf55c7d8d3c527.png)

**优化二**
- 对于剪枝后的搜索树，我们还可以将其转为递推的方式
- 由于我们知道每个数它的前一个数应该是多少，因此我们可以直接从0开始计算

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/eb7064028fd27f33f2e096386d02e67e.png)

代码如下
```java
import java.util.*;

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 2];
        for (int i = 0; i < n; i++) {
            f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
        }
        return f[n - 1 + 2];
    }
}
```

此时的时间复杂度是 $O(n)$，空间复杂度也是 $O(n)$

**优化三**
- 对于 f 数组，我们知道 $当前=max(上一个+上上一个+nums[i])$
- 于是我们可以将 f 数组改成三个变量即可
$$
newF = max(f_{1}, f_{0}+nums[i])
$$
计算完后更新 $f_{1}$ 和 $f_{0}$ 即可
$$
\begin{align}
f_{0}&=f_{1} \\
f_{1}&=newF
\end{align}
$$
代码如下

```java
import java.util.*;

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int f0 = 0, f1 = 0, newF = 0;
        for (int i = 0; i < n; i++) {
            newF = Math.max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = newF;
        }
        return newF;
    }
}
```

这时的事件复杂度是 $O(n)$，空间复杂度就是 $O(1)$ 了

## 494. 目标和

#动态规划 #0-1背包问题

[494. 目标和 - 力扣（LeetCode）](https://leetcode.cn/problems/target-sum/description/)

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/526ae1931f51f3876fb6daf16802e6a4.png)

得到 `0-1背包` 代码

```java
class Solution {
    private int[] w;
    private int[] v;
    private int[] memo;

    /**
     * 背包问题
     * 
     * @param capacity 背包容量
     * @param w        n个物品的体积
     * @param v        n个物品的价值
     * @return 所选物品在不超过capacity的情况下的最大价值
     */
    private int zeroOneKnapsack(int capacity, int[] w, int[] v) {
        int n = w.length;
        this.w = w;
        this.v = v;
        this.memo = new int[n];
        Arrays.fill(this.memo, -1);
        return dfs(n - 1, capacity);
    }

    /**
     * 遍历
     * 
     * @param i 第i个元素
     * @param c 背包容量
     * @return
     */
    private int dfs(int i, int c) {
        if (i < 0) {
            return 0;
        }
        if (this.memo[i] != -1) {
            return this.memo[i];
        }
        if (c < this.w[i]) {
            return dfs(i - 1, c);
        }
        // 选(dfs(i - 1, c - this.w[i]) + this.v[i])或者不选(dfs(i - 1, c))
        int res = Math.max(dfs(i - 1, c), dfs(i - 1, c - this.w[i]) + this.v[i]);
        this.memo[i] = res;
        return res;
    }
}
```

**目标和思路分析**
- 设 $p$ 为所有+号的数之和，那么 $(s-p)$ 就是所有-号的数之和
- 可得

$$
\begin{align}
p-(s-p)&=target \\
2p&=target+s \\
p&=\frac{target+s}{2}
\end{align}
$$
- 变成了规定 target 求 p 的动态规划
代码
```java
import java.util.*;

class Solution {
    private int[] nums;
    private int[][] memo;

    public int findTargetSumWays(int[] nums, int target) {
        // p: nums中的+数
        // ng: s-p nums中的-数 注意，这里不是负数，而是不带-的数的和
        // 可得 p-(s-p)=target
        // 2p=target+s
        // p=(target+s)/2 我们需要求p，计算哪些条件下p是可以满足的
        // (target+s)为偶数 且不为负数(为什么要判断是否为负数，因为target可能为负数，而sum+target可能小于0，则不可能取得结果)
        this.nums = nums;
        target += Arrays.stream(nums).sum();
        if (target < 0 || (target % 2 == 1)) {
            return 0;
        }
        // 除以2去计算p
        target /= 2;

        // 01背包
        int n = nums.length;
        this.memo = new int[n][target + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(this.memo[i], -1);
        }
        return dfs(n - 1, target);
    }

    /**
     * 遍历
     * 
     * @param i 第i个元素
     * @param c 背包容量
     * @return
     */
    private int dfs(int i, int c) {
        if (i < 0) {
            // c == 0表示这些数加起来等于target
            if (c == 0) {
                return 1; // 表示这组合可以 返回1
            }
            // c != 0 表示这些数加起来不等于target
            if (c != 0) {
                return 0; // 表示这组合不行 返回0
            }
        }
        if (this.memo[i][c] != -1) {
            return this.memo[i][c];
        }
        if (c < this.nums[i]) {
            return dfs(i - 1, c);
        }
        // 这里计算了
        int res = dfs(i - 1, c) + dfs(i - 1, c - this.nums[i]);
        this.memo[i][c] = res;
        return res;
    }
}
```