两句话

用户名：uq_42709742140

访问量：3392

签　名：

等　　级
排　　名	2787
经　　验	2149
参赛次数	0
文章发表	37
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

数据结构-Dijskra(迪杰斯特拉)最短路径算法（短代码）
浏览：77

2954: 大整数乘法（C++）借助vector计算
浏览：46

数据结构-Floyd(弗洛伊德)最短路径算法（C++）模板改
浏览：54

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

dfs + DP练习记录（一）

　　作者: 两句话　　　　发表时间：2024-04-12 11:43:22 浏览：63　|　评论：0　

##up的课件：
**链接：**https://www.luogu.com/paste/xac615na

##A823 跳台阶
**链接：**https://www.acwing.com/problem/content/823/

**思路：**
类似斐波那契数列，跳台阶的最后一步可能是跳一个也可能是跳两个，所以情况数就等于i-1 + i-2的总情况数。

**注意：**
f[1]或f[2]输出之后要直接return，否则会输出两次。
空间优化思路，滚动。
```cpp
#include<iostream>
using namespace std;

int f[20];

int main()
{
    int n;
    scanf("%d" , &n);
    
    f[1] = 1 , f[2] = 2;
    if(n == 1 || n == 2)
    {
        printf("%d\n" , f[n]);
        return 0;
    }
    
    int newf = 0 , temp1 = f[1] , temp2 = f[2];
    for(int i = 3;i <= n;i ++)
    {
        // f[i] = f[i - 1] + f[i - 2];	//递推
        newf = temp1 + temp2;	//空间优化
        temp1 = temp2;
        temp2 = newf;
    }
    printf("%d\n" , newf);
    
    return 0;
}
```
##L089 打家劫舍
**链接：**https://leetcode.cn/problems/Gu0c2T/submissions/522756212/

**思路：**
分出子问题，考虑当前这个要不要加入，如果加入则下一次起始要从i+2开始并且加上当前i的值，如果不加入就从i+1开始。
先dfs暴搜，再记忆化搜索优化，最后根据dfs的递归公式改成递推dp，然后倒序

**注意：**
倒序改正序时可能出现数组溢出，i = -1时，则要进行***下标偏移***，for中i的范围不变，仅将dp数组的下标加上一定值，但是其他数组下标不变。
```cpp
#include<iostream>
using namespace std;

int n , a[110];
int f[10010];

int dfs(int x)
{
    if(x > n) return 0;
    else return max(dfs(x + 1) , dfs(x + 2) + a[x]);
}

int main()
{
    scanf("%d" , &n);
    for(int i = 1;i <= n;i ++)
    	scanf("%d" , &a[i]);

// int res = dfs(1);	//直接递归（可配合记忆化搜索）
    // printf("%d\n" , res);

// for(int i = n;i >= 0;i --)
    // {//倒序递推
    //     f[i] = max(f[i + 1] , f[i + 2] + a[i]);
    // }
    // cout<<f[1]<<endl;
    
    for(int i = 1;i < n + 1;i ++)
    {//正序递推，动态规划
        //f[i] = max(f[i - 1] , f[i - 2] + a[i]);   //i的范围不变，直接下标偏移，输出时也要偏移
        f[i + 2] = max(f[i + 1] , f[i] + a[i]);
    }
    cout<<f[n + 2]<<endl;	//i最大为n，i+2 = n+2，故返回n+2

return 0;
}
```
##P1216 数字三角形
**链接：**https://www.luogu.com.cn/problem/P1216

**思路：**
分出子问题，考虑当是要向左下（x+1，y）还是右下（x+1，y+1），比较取两者的最大值然后 + 当前位置的数值（g[x][y]）
先dfs暴搜，再记忆化搜索优化，最后根据dfs的递归公式改成递推dp，然后倒序

**注意：**
数组范围，超出剪枝。
```cpp
#include<iostream>
using namespace std;

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

int dfs(int x , int y)
{
    if(mem[x][y]) return mem[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];
        // return max(dfs(x + 1 , y) + g[x+1][y] , dfs(x + 1 , y + 1) + g[x+1][y+1]);
    mem[x][y] = sum;
    return sum;
        
}
int main()
{
    scanf("%d" , &n);
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= i;j ++)
            scanf("%d" , &g[i][j]);
    
    // int res = dfs(1 , 1);
    // int res = dfs(1 , 1) + g[1][1];
    // printf("%d\n" , res);
    
    // for(int i = n;i >= 1;i --)  //倒序，从下往上推
    //     for(int j = 1;j <= n;j ++)
    //         f[i][j] = max(f[i+1][j] , f[i+1][j+1]) + g[i][j];
    // printf("%d\n" , f[1][1]);
    
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= i;j ++)
            f[i][j] = max(f[i-1][j] , f[i-1][j-1]) + g[i][j];
    int res = 0;
    for(int i = 1;i <= n;i ++)  res = max(res , f[n][i]);
    printf("%d\n" , res);
    
    return 0;
}
```
##A2 01背包
**链接：**https://www.acwing.com/problem/content/2/

**思路：**
分出子问题，考虑当前这个物品的体积，若体积过大则不能加，否则考虑要不要加入，要加的减去体积加上价值，否者同前者。

**注意：**
体积初始为m，放入物品则减去体积
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010;

int mem[N][N];  //从第x个物品开始（x~n）总体积小于等于j的最大价值
int f[N][N];
// int f[N], g[N];
int v[N] , w[N] ;
int n , m , res = 0;

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

int main()
{
    scanf("%d%d" , &n , &m);
    for(int i = 1;i <= n;i ++)
        scanf("%d%d" , &v[i] , &w[i]);
        
    // int res = dfs(1 ,m); //递归及记忆化搜索
    // printf("%d\n" , res);
    
    for(int i = 1;i <= n;i ++)
        for(int j = 0;j <= m;j ++)
        {
            if(v[i] > j)    f[i][j] = f[i-1][j];    //体积不允许不能放时
            else if(v[i] <= j)  //体积允许可以放时
                f[i][j] = max(f[i-1][j] , f[i-1][j - v[i]] + w[i]);
        }
    int res = 0;
    for(int i = 1;i <= m;i ++)
        res = max(res , f[n][i]);
    printf("%d\n" , f[n][m]);
    
    // for(int i = 1;i <= n;i ++)
    // {
    //     for(int j = 0;j <= m;j ++)
    //     {
    //         if(v[i] > j)    g[j] = f[j];    //体积不允许不能放时
    //         else if(v[i] <= j)  //体积允许可以放时
    //             g[j] = max(f[j] , f[j - v[i]] + w[i]);
    //     }
    //     memcpy(f , g , sizeof f);
    // }
    // printf("%d\n" , f[m]);
    
    return 0;
}
```
##A2 完全背包
**链接：**https://www.acwing.com/problem/content/2/

**思路：**
分出子问题，考虑当前这个物品的体积，若体积过大则不能加，否则考虑要不要加入，要加的减去体积加上价值，否者同前者。

**注意：**
体积初始为m，放入物品则减去体积
完全背包可以重复放置，如果当前物品不放则下一位从x+1开始，若当前物品放入**选择时下一位的起始值为x（可以重复拿）**
（注意与01背包比较，一维滚动数组的时候要考虑完全正序，01倒序，当前二维可以不考虑）
```cpp
#include<iostream>
using namespace std;

const int N = 1010;
int v[N] , w[N];
int mem[N][N] , f[N][N];
int n , V;

int dfs(int x , int spv)
{
    if(mem[x][spv]) return mem[x][spv];
    if(x > n)   return 0;  //终止标志
    
    int sum = 0;
    if(spv < v[x]) sum = dfs(x + 1 , spv);
    else 
        sum = max(dfs(x + 1 , spv) , dfs(x, spv-v[x]) + w[x]);
    
    mem[x][spv] = sum;
    return sum;
}

int main()
{
    scanf("%d%d" , &n , &V);
    for(int i = 1;i <= n;i ++)
    	scanf("%d%d" , &v[i] , &w[i]);
    
    // int res = dfs(1 , V);
    // printf("%d\n" , res);
    
    for(int i = 1;i <= n;i ++)
        for(int j = 0;j <= V;j ++)
        {
            if(j < v[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j] , f[i][j - v[i]] + w[i]);
        }
    printf("%d\n" , f[n][V]);
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

两句话

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

回文数字（C++代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

dfs + DP练习记录（一）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

程序员的表白（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言训练-求PI* （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

两句话

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

回文数字 （C++代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

dfs + DP练习记录（一）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

程序员的表白 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言训练-求PI* （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

回文数字（C++代码）

C二级辅导-进制转换（C语言代码）

　　评论区

程序员的表白（C语言代码）