动态规划入门

原题单链接：https://rentry.org/2f76axt4

见到很有意思的问题 : 以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。(看到一位知乎的大佬说的, 深有感悟~)

动态规划 就是 : 给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法.

那么我们今天就来带给大家 新手入门动态规划的正确方法!

记忆化搜索 = 暴力dfs + 记录答案

动态规划入门思路: dfs暴力 — 记忆化搜索 — 递推

1dfs > 2记忆化搜索 > 3逆序递推 > 4顺序递推 > 5优化空间 !

递归的过程:

“递” 的过程是: 分解子问题的过程;

“归” 的过程才是: 产生答案的过程;

“递” – 自顶向下, “归” – 自底向上 ，其中 “底” 是 递归搜索树 的底

写出递推公式的方法:

递推的公式 = dfs 向下递归的公式

递推数组的初始值 = 递归的边界

例题

acwing821.跳台阶 \或者\ P1255. 数楼梯

#include 

using namespace std;

const int N = 100;
int n;
int f[N];

int main()
{
    f[1] = 1, f[2] = 2;
    cin >> n;
    int newf = 0, tmp1 = 1, tmp2 = 2;
    for(int i = 3; i 

using namespace std;

const int N = 100010;
int n, T;
int home[N];
int men[N];
int f[N];

int dfs(int x)
{
    if (men[x])
        return men[x];

    int sum = 0;
    if (x > n)
        sum = 0;
    else
        sum = max(dfs(x + 1), dfs(x + 2) + home[x]);

    men[x] = sum;
    return sum;
}

int main()
{
    cin >> T;
    while (T--)
    {
        memset(men, 0, sizeof men);
        cin >> n;
        for (int i = 1; i > home[i];
        }
        // int res = dfs(1);
        // cout = 1; i--)
        // {
        //     f[i] = max(f[i+1],f[i+2]+home[i]);
        // }
        // cout 

using namespace std;

const int N = 1010;
int n;
int g[N][N];
int mem[N][N];
int f[N][N];
int h[N];

int dfs(int x, int y)
{
    if (mem[x][y])
        return mem[x][y];

    // if (x>n||y>n) return 0;
    // // 求 最优子问题 dfs(x)=max(dfs(x+1),dfs(x+2))
    // // 求 子问题的和 dfs(x)=dfs(x+1)+dfs(x+2)
    // else return max(dfs(x+1,y),dfs(x+1,y+1))+g[x][y];
    int sum = 0;
    if (x > n || y > n)
        sum = 0;
    else
        sum = max(dfs(x + 1, y), dfs(x + 1, y + 1)) + g[x][y];
    mem[x][y] = sum;
    return sum;
}

int main()
{
    cin >> n;
    for (int i = 1; i > g[i][j];
    // int res = dfs(1, 1);
    // cout = 1; i -- )
    //     for (int j = 1; j = 1; i--)
    //     for (int j = 1; j = 1; i--)
        for (int j = 1; j 
#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int res = 0;

void dfs(int x, int sumV, int sumW)
{
    if (x > n)
    {
        if (sumV = res)
        {
            res = sumW;
        }
        return;
    }

    // 不选
    dfs(x + 1, sumV, sumW);

    // 选
    if (sumV + v[x] 
#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int res = 0;
int mem[N][N];
int f[N][N];
int g[N];

int dfs(int x, int spV)
{
    if (mem[x][spV])
    {
        return mem[x][spV];
    }

    int sum = 0;
    if (x > n)
    {
        sum = 0;
    }
    else if (spV = v[x])
    {
        sum = max(dfs(x + 1, spV), dfs(x + 1, spV - v[x]) + w[x]);
    }
    mem[x][spV] = sum;
    return sum;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i = 1; i--)
    // {
    //     for (int j = 0; j = v[i])
    //         {
    //             f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);
    //         }
    //     }
    // }
    // cout= v[i])
            {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    cout 

## 下期待更新的dp题单（2024.2.25编）

### [LCR 091. 粉刷房子](https://leetcode.cn/problems/JEj789/) 简单dp

### [413. 等差数列划分](https://leetcode.cn/problems/arithmetic-slices/) 如果满足等差，则f[i] = f[i - 1] + 1, 否则为0

### [279. 完全平方数](https://leetcode.cn/problems/perfect-squares/) 简单预处理，最后一步：选择某个数作为最后一个

### [91. 解码方法](https://leetcode.cn/problems/decode-ways/) 正序dfs好写

### [646. 最长数对链](https://leetcode.cn/problems/maximum-length-of-pair-chain/) 最长上升子序列模板 + 排序

### [918. 环形子数组的最大和](https://leetcode.cn/problems/maximum-sum-circular-subarray/) 找找最大和 、 最小和 和 总和的关系

### [376. 摆动序列](https://leetcode.cn/problems/wiggle-subsequence/) 考虑相邻两个数大小问题，枚举选哪个模型，dp转移可以直接**01转移**

### [2786. 访问数组中的位置使分数最大](https://leetcode.cn/problems/visit-array-positions-to-maximize-score/) 枚举每个数选或不选，记录上的数的奇偶性，**01转移** 实现dfs不需要传vector的参数

### [213. 打家劫舍 II](https://leetcode.cn/problems/house-robber-ii/) 考虑选不选第一个物品，可以把问题分为两个子问题

### [122. 买卖股票的最佳时机 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/) 状态机模型

### [368. 最大整除子集](https://leetcode.cn/problems/largest-divisible-subset/) pre数组**记录路径**，更新时实现记录，而不是以前的max不知道更新没更新

### [1105. 填充书架](https://leetcode.cn/problems/filling-bookcase-shelves/) 枚举选哪个，**转移方程**有教学意义

### [1416. 恢复数组](https://leetcode.cn/problems/restore-the-array/) 枚举选哪个，**集合转移**

### [2466. 统计构造好字符串的方案数](https://leetcode.cn/problems/count-ways-to-build-good-strings/) 爬楼梯

### [1043. 分隔数组以得到最大和](https://leetcode.cn/problems/partition-array-for-maximum-sum/) 枚举选哪个，**集合转移**

### [2400. 恰好移动 k 步到达某一位置的方法数目](https://leetcode.cn/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/) 要对mem数组做偏移，`mem[now + N][cnt]` ，选其中一个的思路

### [1335. 工作计划的最低难度](https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/) 枚举选哪个思路，**集合转移**

### [7006. 销售利润最大化](https://leetcode.cn/problems/maximize-the-profit-as-the-salesman/) **集合转移**， 预处理endi，选或不选

### [2008. 出租车的最大盈利](https://leetcode.cn/problems/maximum-earnings-from-taxi/) 选或不选

### [1235. 规划兼职工作](https://leetcode.cn/problems/maximum-profit-in-job-scheduling/) 选或不选 [1751. 最多可以参加的会议数目 II](https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended-ii/) 类似 [2054. 两个最好的不重叠活动](https://leetcode.cn/problems/two-best-non-overlapping-events/)

## 01转移

### [376. 摆动序列](https://leetcode.cn/problems/wiggle-subsequence/) 考虑相邻两个数大小问题，枚举选哪个模型，dp转移可以直接01转移

### [2786. 访问数组中的位置使分数最大](https://leetcode.cn/problems/visit-array-positions-to-maximize-score/) 枚举每个数选或不选，记录上的数的奇偶性

### [122. 买卖股票的最佳时机 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/) 状态机模型

### [1186. 删除一次得到子数组最大和](https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/) 子数组最大和 + 记录删没删

### [2369. 检查数组是否存在有效划分](https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/) **划分型dp** 好像用不了记忆化搜索？

### [2466. 统计构造好字符串的方案数](https://leetcode.cn/problems/count-ways-to-build-good-strings/) 爬楼梯