算法基础-----【动态规划】

动态规划(待完善)

动规五部曲分别为：

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式（状态转移公式）
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组、

动态规划的核心就是递归+剪枝（存储键值，下次不再访问，用空间换时间）

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？
或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

​ 动态规划的解题步骤：（1）确定dp数组以及下标含义 （2）确定递推公式 （3）dp数组如何初始化 （4）确定遍历顺序 （5）例举推导dp数组。

【基础题目】

【509】斐波那契数列

解题步骤：

1）确定dp数组以及下标含义

dp[i]: 第i个数的斐波那契数值是dp[i]。

2）确定递推公式

dp[i] = dp[i-1]+dp[i-2]

3）dp数组如何初始化

dp[0] = 0 dp[1] = 1

4）确定遍历顺序

从前向后遍历

5）例举推导dp数组。

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

//动态规划基础问题
/*递归的方法 ：时间复杂度o(n^2) 空间复杂度o(1)*/
class Solution {
public:
    int fib(int n) {
        if(n<2)return n;
        return fib(n-1)+fib(n-2);
    }
};
/*动态规划的方法 时间复杂度o(n) 空间复杂度o(n)(经典做法)*/
class Solution {
public:
    int fib(int n) {
        if(n<2)return n;
        vector<int> dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i<n+1;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

/*动态规划简写 时间复杂度o(n) 空间复杂度o(1)*/
class Solution {
public:
    int fib(int n) {
        if(n<2)return n;
        vector<int> dp(2);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i<n+1;i++){
            int sum = dp[0]+dp[1];
            dp[0] = dp[1]; 
            dp[1] = sum;
        }
        return dp[1];
    }
};

【70】爬楼梯

确定递归数列：找规律 f(n) = f(n-1)+f(n-2)
确定终值f(1) = 1 f(0) = 0
存储节点：定义数组存储节点
最标准的做法，要是还要优化空间复杂度就考虑上面的做法

class Solution {
public:
    int climbStairs(int n) {
        if(n<2)return n;//(f(1)= 1,f(2) =2)
        vector<int> f(n+1);
        f[1] =1;
        f[2] =2;
        for(int i =3;i<n+1;i++){
            f[i] =f[i-1]+f[i-2];
        }
        return f[n];
    }
};

【118】杨辉三角

注意申请数组具体那一行
注意改变数组的长度的函数resize(为了防止0出现)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};

【198】打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

按照五部曲进行推导

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        //确定dp数组 dp[i]存放最高金额
        vector<int> dp(n);
        if(n == 0)return 0;
        if(n == 1)return nums[0];
        if( n == 2)return max(nums[0],nums[1]);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);

        for(int i = 2;i<n;i++){
            dp[i] = max(dp[i-1],nums[i]+dp[i-2]);
            cout<<dp[i]<<endl;
        }
        return dp[n-1];
    }
};

【背包问题】

【0-1背包】

对于面试，掌握01背包和完全背包，多重背包。
在这里插入图片描述

基础引用：对于0，1背包，就是m个物品，给定对应的重量和价值，最大容量为n，这些物品你只能选一个或者不选（01），求最大价值。
在这里插入图片描述

动态规划五部曲：

（1）确定dp数组以及下标的含义dp[i] [j ]:表示下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

（2）确定递推公式：

  • 放物品i：由dp[i - 1] [j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i] [j]就是dp[i - 1] [j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
  • 放物品i：由dp[i - 1] [j - weight[i]]推出，dp[i - 1] [j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1] [j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]);

（3）初始化dp数组

​ 后面的公式是根据前面来推导的，所以初始化正确了才能导致dp数组正确

​ 状态转移方程 dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

​ 要求出 dp[ 0 ] [ j]:也就是求种类0在不同重量下的最大价值：当j<weight[0]的时候肯定装不下，都为0.所以j从weight[0]开始初始化，都为value[0]:

在这里插入图片描述

(4)确定遍历顺序：先遍历物品，再遍历重量：

for(int i =1;i<m;i++){
    for(int j = 0;j<=m;j++){
        if(j<weight[i]){
            dp[i][j] = dp[i-1][j];//不放
        }else{
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);//放
        }
    }
}

在这里插入图片描述

（5）举例推导dp数组

image-20240429141403376 
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution{
public:
   int maxSolution( vector<int>& weight,vector<int>& value,int m,int n){
       //确定dp数组
       vector<vector<int>> dp(m,vector<int>(n+1,0));//要包含一个0
       //初始化dp数组 dp[i-1][j] 初始化 dp[0][j]
        for(int j = weight[0];j<=n;j++){
            dp[0][j] = value[0];
        }

        for(int i =1;i<m;i++){//遍历背包种类 种类1已经初始化过了，要从2开始
            for(int j = weight[0];j<=n;j++){//遍历重量
                if(j<weight[i])dp[i][j] = dp[i-1][j];
                else dp[i][j]= max( dp[i-1][j-weight[i]]+value[i],dp[i-1][j]);

            }
        }
        cout<<dp[m-1][n]<<endl;
   }


};


int main()
{
    int m;//背包种类
    int n;//空间容量 bagweight
    vector<int> weight(m,0);
    vector<int> value(m,0);
//    cin >>m>>n;
//    for(int i =0;i<m;i++){
//        cin>> cap[i];
//    }
//    for(int i =0;i<m;i++){
//        cin>> value[i];
//    }
    m = 3;//背包种类
    n = 4;//最大容量是4
    weight = {1,3,4};//重量
    value = {15,20,20};//价值
    Solution s;
    int res = s.maxSolution(weight,value,m,n);
    return 0;
}

【416】分割等和子集

​ 0-1背包是可以用回溯的方式去做的，和【698】【473】都有相同的做法。

​ 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

j:容量，dp[j]最大价值，可以看到都是倒叙取最大值，最后的dp数组是：

01234567891011
01111566661011

在这里插入图片描述

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum =0;
        for(auto num:nums){
            sum+=num;
        }
        if(sum%2 == 1)return false;//要是不能平分直接退出
        int n = sum/2;
        vector<int> dp(n+1,0);//初始化dp数组

        //dp遍历
        for(int i =0;i<nums.size();i++){
            for(int j=n;j>=nums[i];j--){//特别注意这个nums[i]
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
                cout<<"i:"<<i<<" dp["<<j<<"]:"<<dp[j]<<endl;
            }
        }
        //判断
        if(dp[n] == n)return true;
        return false;
    }
};

【1049】最后一块石头的重量

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int sum =0;
        for(auto item:stones){
            sum+=item;
        }
        int target = sum/2;
        vector<int> dp(target+1,0);
        for(int i =0;i<n;i++){
            for(int j = target;j>=stones[i];j--){
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];//注意最后返回的数值
    }
};

【494】目标和

【17】一和零

【完全背包】

完全背包内层循环从头开始

【322】零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //初始化dp数组
        vector<int> dp(amount+1,INT_MAX);
        dp[0] = 0;
        for(int i =0;i<coins.size();i++){
            for(int j = coins[i];j<=amount;j++){//遍历背包 注意初始化的位置
                if(dp[j-coins[i]] !=INT_MAX){// 如果dp[j - coins[i]]是初始值则跳过
                    dp[j] = min(dp[j],dp[j-coins[i]]+1);
                }

            }
        }
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

遍历的过程：

以coins = [1,2,5]，amount = 11为例子：

01234567891011
初始化0MMMMMMMMMMM
1(只有1)01234567891011
2（1或2）011223344556
5（1或2或5）011221223323

【139】单词拆分

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //存储wordDict 背包
        unordered_set<string> wordMap(wordDict.begin(),wordDict.end());
        vector<int> dp(s.size()+1,false);//dp数组
        dp[0]= true;
        //求的是排列数，有顺序，背包在外层
        for(int i =1;i<=s.size();i++){//遍历背包
            for(int j =0;j<i;j++){//遍历物品
                string tmp = s.substr(j,i-j);
                if(wordMap.find(tmp)!= wordMap.end()&&dp[j] == true){
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];

    }
};

【子序列问题】

【300】最长子序列

（1)根据返回值确定dp[i]:以nums[i]结尾的最长子序列的数组长度。

（2)状态转移方程： if(nums[i]>nums[j])dp[i] = max(dp[i],dp[j]+1);（往前对比）

（3）dp数组初始化，dp[i] = 1

(4) 确定遍历顺序，dp[i+1] = dp[i]

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int res =1;
        if(nums.size() == 1)return 1;
        if(nums.size() == 0)return 0;

        vector<int> dp(nums.size(),1);
        
        for(int i =1;i<nums.size();i++){
            for(int j = 0;j<i;j++){
                if(nums[i]>nums[j])dp[i] = max(dp[i],dp[j]+1);
            }
            if(dp[i]>res)res = dp[i];//不一定是最后一个元素，取最长子序列
        }
        return res;
    }
};

【301】

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/755278.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

有人物联的串口服务器USR-TCP232-410S基本测试通信和使用方案（485串口和232串口）

有人物联的串口服务器USR-TCP232-410S基本测试通信和使用方案（485串口和232串口）

1.将 410S(USR-TCP232-410S&#xff0c;简称 410S 下同)的串口通过串口线(或USB 转串口线)与计算机相连接&#xff0c;通过网线将 410S 的网口 PC 的网口相连接&#xff0c;检测硬件连接无错误后&#xff0c;接入我们配送的电源适配器&#xff0c;给 410S 供电。观察指示灯状态…
阅读更多...
Python面试宝典第1题：两数之和

Python面试宝典第1题：两数之和

题目 给定一个整数数组 nums 和一个目标值 target&#xff0c;找出数组中和为目标值的两个数的索引。可以假设每个输入只对应唯一的答案&#xff0c;且同样的元素不能被重复利用。比如&#xff1a;给定 nums [2, 7, 11, 15] 和 target 9&#xff0c;返回 [0, 1]&#xff0c;因…
阅读更多...
《数据仓库与数据挖掘》 总复习

《数据仓库与数据挖掘》 总复习

试卷组成 第一章图 第二章图 第三章图 第四章图 第五章图 第六章图 第九章图 第一章 DW与DM概述 &#xff08;特点、特性&#xff09; DB到DW 主要特征 &#xff08;1&#xff09;数据太多&#xff0c;信息贫乏&#xff08;Data Rich&#xff0c; Information Poor)。 &a…
阅读更多...
计算机网络 —— 路由协议：RIP、OSPF、BGP、MPLS

计算机网络 —— 路由协议：RIP、OSPF、BGP、MPLS

路由协议 1. 定义2. IGP2.1 RIP2.2 OSPF 3. BGP4. MPLS 1. 定义 互联网中需要通过路由将数据发送至目标主机。 路由器根据**路由控制表(RoutingTable)**转发数据包&#xff0c;它根据所收到的数据包中目标主机的IP地址与路由控制表的比较得出下一个应该接收的路由器。 &…
阅读更多...
HarmonyOS ArkUi ArkWeb加载不出网页问题踩坑

HarmonyOS ArkUi ArkWeb加载不出网页问题踩坑

使用 使用还是比较简单的&#xff0c;直接贴代码了 别忘了配置网络权限 Entry Component struct WebPage {State isAttachController: boolean falseState url: string State title: string Prop controller: web_webview.WebviewController new web_webview.WebviewCont…
阅读更多...
【opencv - C++ - Ubuntu】putText 显示中文最快方法

【opencv - C++ - Ubuntu】putText 显示中文最快方法

话不多说&#xff0c;直接上代码 #include <iostream> #include <opencv2/opencv.hpp> #include <opencv2/freetype.hpp>using namespace std; using namespace cv;int main(void) {Mat image(1000, 1800, CV_8UC3, Scalar(200,162,33));Ptr<freetype::F…
阅读更多...
一篇大模型 Agent 工具使用全面研究综述

一篇大模型 Agent 工具使用全面研究综述

使用大型语言模型&#xff08;LLMs&#xff09;进行工具学习已成为增强LLMs能力以解决高度复杂问题的一个有希望的范式。尽管这一领域受到越来越多的关注和快速发展&#xff0c;但现有的文献仍然分散&#xff0c;缺乏系统性的组织&#xff0c;为新来者设置了进入障碍。因此对LL…
阅读更多...
Gemma 2大模型：性能更优，效率更高

Gemma 2大模型：性能更优，效率更高

当地时间6月27日&#xff0c;谷歌正式发布了在一个月前的I/O开发者大会上预告过的Gemma 2大模型。这款新模型相较于第一代Gemma模型&#xff0c;在性能和推理效率上都有了显著的提升&#xff0c;为AI领域带来了新的突破。 据谷歌介绍&#xff0c;Gemma 2模型包括9B和27B两种参…
阅读更多...
AIGC-＞基于扩散模型的图像生成算法 (课程大纲)

AIGC-＞基于扩散模型的图像生成算法 (课程大纲)

https://edu.csdn.net/course/detail/39618?spm=1001.2014.3001.5507https://edu.csdn.net/course/detail/39618?spm=1001.2014.3001.5507 课程特色是围绕着工作中AIGC文生图的具体用途来对文生图领域进行一个高屋建瓴式的分析，结合具体的应用，尤其是产业界的具体实用场景，…
阅读更多...
【排序算法】—— 希尔排序

【排序算法】—— 希尔排序

目录 一、希尔排序原理 二、希尔排序的思路 三、希尔排序为什么快 四、如何取增量 五、源码 希尔排序是简单插入排序的一种升级版&#xff0c;它也是用了插入的思想&#xff0c;而插入排序相比冒泡排序和选择排序的效率要高的多&#xff0c;再将它优化为希尔排序后效率跟原…
阅读更多...
ONLYOFFICE 桌面编辑器 8.1 发布：全新 PDF 编辑器、幻灯片版式、增强 RTL 支持及更多本地化选项

ONLYOFFICE 桌面编辑器 8.1 发布：全新 PDF 编辑器、幻灯片版式、增强 RTL 支持及更多本地化选项

目录 什么是ONLYOFFICE&#xff1f; ONLYOFFICE 主要特点包括&#xff1a; 官网信息&#xff1a; 1. 功能齐全的 PDF 编辑器 1.1 编辑 PDF 文本 1.2 插入和修改对象 1.3 创建和填写表单 2. 幻灯片版式功能 2.1 快速应用幻灯片版式 2.2 动画窗格的改进 3. 文档编辑、…
阅读更多...
Linux—系统安全及应用

Linux—系统安全及应用

目录 一、账号安全控制 1、系统账号清理 1.1、将用户账号设置为无法登录 1.2、锁定长期不使用的账号 1.3、删除无用的账号 1.4、锁定账号文件passwd、shadow 2、密码安全控制 2.1、设置密码有效期 2.1.1、适用于新建用户 2.1.2、适用于已有用户 2.2、强制用户下次登录…
阅读更多...
什么是预主密钥（pre-master secret）？

什么是预主密钥（pre-master secret）？

什么是预主密钥&#xff08;Pre-Master Secret&#xff09;&#xff1f; 在SSL/TLS协议中&#xff0c;预主密钥&#xff08;Pre-Master Secret&#xff09;是建立安全连接的关键要素之一。它在客户端和服务器之间生成共享密钥的过程中扮演重要角色。本文将详细介绍预主密钥的生…
阅读更多...
Raylib学习-鼠标检测与GPU缓冲区使用

Raylib学习-鼠标检测与GPU缓冲区使用

鼠标左键点击运行绘制 #include <raylib.h>int main() {const int screenWidth 800;const int screenHeight 450;InitWindow(screenWidth, screenHeight, "test"); // 设置帧率SetTargetFPS(150); // 设置一个画布&#xff0c;可以使用GPU进行绘制RenderText…
阅读更多...
k8s部署mongodb副本高可用集群

k8s部署mongodb副本高可用集群

此版本的NFS为单点，仅为练习使用，生产环境建议使用cephfs的卷类型，避免单点。或者通过keepalived加Sersync的方案对NFS作容灾处理即可用于生产环境。当然，对于开发或测试环境，方便起见，直接使用单点的NFS加mongodb statefulSet方案是最为清晰简便的。 mongodb集群部署分…
阅读更多...
2024年每个月有哪些数学建模和数学挖掘竞赛？

2024年每个月有哪些数学建模和数学挖掘竞赛？

文章目录 2024年每个月有哪些竞赛&#xff1f;2024年32个数学建模和数据挖掘竞赛重磅来袭&#xff01;&#xff01;&#xff01;2024年数学建模和数学挖掘竞赛时间目录汇总数学建模助手使用一月二月三月四月五月六月七月八月九月十月十一月十二月 2024年每个月有哪些竞赛&#…
阅读更多...
Interview preparation--Elasticsearch写入原理与调优

Interview preparation--Elasticsearch写入原理与调优

ES的写入过程 ES支持的写操作 create&#xff1a; create操作不同于put操作&#xff0c;put操作的时候如果当前put的数据存在则会被覆盖&#xff0c;如果put操作的时候加上操作类型create&#xff0c;如果数据存在则会返回失败&#xff0c;比如&#xff1a;PUT /pruduct/_cre…
阅读更多...
【项目日记（二）】搜索引擎-索引制作

【项目日记（二）】搜索引擎-索引制作

❣博主主页: 33的博客❣ ▶️文章专栏分类:项目日记◀️ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; &#x1faf5;&#x1faf5;&#x1faf5;关注我带你了解更多项目内容 目录 1.前言2.索引结构2.1创捷索引2.2根据索引查询2.3新增文档2.4内存索引保存到磁盘2.5把…
阅读更多...
VUE的快速使用

VUE的快速使用

使用步骤 代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title> </head&…
阅读更多...
数据结构历年考研真题对应知识点（串的模式匹配）

数据结构历年考研真题对应知识点（串的模式匹配）

目录 4.2串的模式匹配 4.2.2串的模式匹配算法——KMP算法 【KMP 匹配过程中指针变化的分析(2015)】 【KMP 匹配过程中比较次数的分析(2019)】 4.2串的模式匹配 4.2.2串的模式匹配算法——KMP算法 【KMP 匹配过程中指针变化的分析(2015)】 最终得到子串指针变化公式 jnex…
阅读更多...
最新文章

Copyright @ 2022~2023