两句话

用户名：uq_42709742140

访问量：3392

签　名：

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

　　自我简介：

TA的其他文章

Seq2Seq的学习总结
浏览：50

你可能喜欢

dfs + DP练习记录（二）

　　作者: 两句话　　　　发表时间：2024-04-12 17:39:14 浏览：53　|　评论：0　

##A8 二维费用的背包问题
**链接：**https://www.acwing.com/problem/content/8/

**思路：**
与一维背包思路相同，但是要多加一个判断条件

**注意：**
注意各数组的含义，别搞错了！！
```cpp
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
int v[N] , w[N] , m[N];
int f[110][110];
int n , V , M;

int dfs(int x , int spv , int spm)
{
    if(x > n)
    {
        return 0;
    }
    else 
    {
        if(spv >= v[x] && spm >= m[x])  //别搞错了各个数组的含义！！
            return max(dfs(x + 1 , spv , spm) , dfs(x + 1 , spv-v[x] , spm-m[x]) + w[x]);
        else return dfs(x + 1 , spv , spm);
    }
}

int main()
{
    scanf("%d%d%d" , &n , &V , &M);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d%d%d" , &v[i] , &m[i] , &w[i]);
    }
    
    // int res = dfs(1 , V , M);
    // printf("%d\n" , res);
    
    for(int i = 1;i <= n;i ++)
        for(int j = V;j >= 0;j --)
            for(int k = M;k >= 0;k --)
            {
                if(j < v[i] || k < m[i])
                    f[j][k] = f[j][k];
                else
                    f[j][k] = max(f[j][k] , f[j - v[i]][k - m[i]] + w[i]);
            }
    printf("%d\n" , f[V][M]);
    
    return 0;
}
```
##L746 使用最小花费爬楼梯
**链接：**https://leetcode.cn/problems/min-cost-climbing-stairs/description/

**思路：**
每次只能走一个或两个楼梯，则把最后一个子问题分离出来，判断是从n-2走两个楼梯上来还是从n-1走一个楼梯上来，分别加上对应价值

**注意：**
dfs是由n到1，所以dp直接从1到n正序即可
```cpp
const int N = 1010;
class Solution {
public:
    int mem[N];
    int f[N];
    int dfs(vector<int>& cost , int x)
    {
        if(mem[x]) return mem[x];
        if(x <= 0 || x == 1) return 0;

int res = 0;
        res =  min(dfs(cost , x - 1) + cost[x - 1] , dfs(cost , x - 2) + cost[x - 2]);
        mem[x] = res;
        return res;
    }
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        // int res = dfs(cost, n);
        f[1] = 0 , f[0] = 0;
        for(int i = 2;i <= n;i ++)
        {
            f[i] = min(f[i-1] + cost[i-1] , f[i-2] + cost[i-2]);
        }
        return f[n];
    }
};
```
##L300 最长上升子序列
**链接：**https://leetcode.cn/problems/longest-increasing-subsequence/submissions/522890327/

**思路：**
判断以第i位数结尾的、上升子序列的最大值（如果在它前面的数字 j 比他小，就判断是将当前数字加入组成的子序列长，还是不加入更长，如果加入则求以j 结尾的最长子序列的长度再 + 1，不加入则直接是当前值，**不加入的情况下直接用ans表示**不能再搜索dfs(num , i），最后循环求所有最大值中最大的一个

**注意：**
dfs是由n到1，所以dp直接从1到n正序即可
```cpp
const int N = 10010;
class Solution {
public:
    int mem[N];    //优化至记忆化搜索，时间复杂度仍然较高
    int f[N];	//动态规划
    int dfs(vector<int>& nums , int x)
    {
        int n = nums.size();
        int ans = 0;
        if(mem[x]) return mem[x];
        if(x > n || x < 0)   return 0;

for(int i = x;i >= 0;i --)
        {//查找以当前数字为末尾值的最大上升子序列
            if(nums[i] < nums[x])
            ans = max(ans , dfs(nums , i) + 1);
        }
        mem[x] = ans;
        return ans;
    }
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int res = -1e9;
        // for(int i = 0;i < n;i ++)
        // {//暴力dfs
        //     res = max(res , dfs(nums , i));
        // }
        // return res + 1;  //加一是因为当前数字i并没有被算入

for(int i = 0;i < n;i ++)
        {
            f[i] = 1;
            for(int j = i;j >= 0;j --)
            {
                if(nums[i] > nums[j])
                    f[i] = max(f[i] , f[j] + 1);
            }
        }
        for(int i = 0;i < n;i ++) res = max(res , f[i]);
        return res;
    }
};
```

```cpp
const int N = 10010;

class Solution {
public:
    int mem[N];
    int dfs(vector<int>& coins , int amount)
    {
        if(mem[amount]) return mem[amount];
        if(amount == 0) return 0;
        if(amount < 0) return 1e9;

int n = coins.size();
        int res = 1e9;
        for(int i = 0;i < n;i ++)
        {
            if(amount >= coins[i])
                res = min(res , dfs(coins , amount - coins[i])+1);
        }
        mem[amount] = res;
        return res;
    }

int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        // int ans = dfs(coins , amount);
        // if(ans == 1e9) return -1;
        // else return ans;

int f[N];
        memset(f , 0x3f , sizeof f);
        f[0] = 0;
        for(int i = 0;i <= amount;i ++)
            for(int j = 0;j < n;j ++)
            {
                if(i >= coins[j])
                    f[i] = min(f[i] , f[i - coins[j]] + 1);
            }
        if(f[amount] >= 0x3f3f3f3f / 2) return -1;
        else return f[amount];
    }
};
```
##L322 零钱兑换
**链接：**https://leetcode.cn/problems/coin-change/

**思路：**
判断当前的第i个零钱是否小于总数，若小于可参与兑换，最后计算参与兑换的硬币数量，每次都从0-1遍历一遍coin数组（**可重复选择**）

**注意：**
能够重复选择所以每一次dfs都遍历数组
```cpp
const int N = 10010;

int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        // int ans = dfs(coins , amount);
        // if(ans == 1e9) return -1;
        // else return ans;

int f[N];
        memset(f , 0x3f , sizeof f);
        f[0] = 0;
        for(int i = 0;i <= amount;i ++)
            for(int j = 0;j < n;j ++)
            {
                if(i >= coins[j])
                    f[i] = min(f[i] , f[i - coins[j]] + 1);
            }
        if(f[amount] >= 0x3f3f3f3f / 2) return -1;
        else return f[amount];
    }
};
```
##A55 连续子数组的最大和
**链接：**https://www.acwing.com/problem/content/50/

**思路：**
判断当前数字是加上前面的**最大和（dfs(num , i-1)）**更大，还是不加上更大

**注意：**
子数组：需要连续不能跳跃
子序列：可以不连续
```cpp
const int N = 1010;
class Solution {
public:
    int mem[N];
    int dfs(vector<int>& nums , int x)
    {
        if(x < 0) return 0;
        if(mem[x])  return mem[x];  //由dfs到记忆化搜索

int res = -1e9;
        int n = nums.size();
        res = max(nums[x] , dfs(nums , x - 1) + nums[x]);	//递推公式（不需要像子序列一样循环因为不用判断大小）
        mem[x] = res;
        return res;
    }
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int ans = -1e9;
        // for(int i = 0;i < n;i ++)
        // {
        //     ans = max(ans , dfs(nums , i));
        // }

int f[N];
        for(int i = 0;i < n;i ++)
        {//若存在越界问题，则将f下的偏移量+1，下方遍历时的起止位置也要+1
            //f[i] = max(nums[i] , f[i - 1] +nums[i]);
			f[i + 1] = max(nums[i] , f[i] + nums[i]);
        }
        for(int i = 1;i <= n;i ++)
            ans = max(ans , f[i]);

return ans;
    }
};
```
##L343 整数拆分
**链接：**https://leetcode.cn/problems/integer-break/

**思路：**
对于x进行递归拆数字就是(dfs(x-i) , i),拆一个i和一组dfs(x-i)，相当于一个一个的拆。

**注意：**
**至少需要拆出来两个数**，所以先比较拆出来两个数（i , x-i）的积与拆出若干个数(dfs(x - i) , i)的积谁大，再比较这些中最大的那个
```cpp
const int N = 65;
class Solution {
public:
    int mem[N];
    int dfs(int x)
    {
        if(x == 0) return 1;
        if(mem[x]) return mem[x];
        int res = 0;
        for(int i = 1;i < x;i ++)
        {//至少拆出来两个数，即i和x - i的情况
            res = max(res ,max(i * (x - i) ,dfs(x - i) * i)) ;
        }
        mem[x] = res;
        return res;
    }
    int integerBreak(int n) {
        // return dfs(n);
        int f[N];

for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j < i;j ++)
            {
                f[i] = max(f[i] , max(j * (i - j) , f[i - j] * j));
            }
        }
        return f[n];
    }
};
```

0.0分

0 人评分

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

两句话

TA的其他文章

你可能喜欢

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

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

Tom数（C语言代码）

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

点我有惊喜！你懂得！

dfs + DP练习记录（二）

评论区

精彩推荐

母牛的故事（C语言代码）

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

【明明的随机数】（C++代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

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

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

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

1014题解

剪刀石头布（C++代码）

1050题解（结构体数组与结构体指针的使用）

两句话

TA的其他文章

你可能喜欢

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

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

Tom数 （C语言代码）

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

点我有惊喜！你懂得！

dfs + DP练习记录（二）

评论区

精彩推荐

母牛的故事 （C语言代码）

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

【明明的随机数】 （C++代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

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

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

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

1014题解

剪刀石头布 （C++代码）

1050题解（结构体数组与结构体指针的使用）

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

Tom数（C语言代码）

　　评论区

母牛的故事（C语言代码）

【明明的随机数】（C++代码）

剪刀石头布（C++代码）