动态规划算法

一、前言

动态规划是一种常用的算法,在算法领域十分重要,但对于新手来说,理解起来有一定的挑战性,这篇博客将明确步骤来一步一步讲解动态规划到底该如何理解与运用。

二、解析动态规划算法

1.特点

①把原来的问题分解成了【要点相同】的子问题(这个要点可以和后面讲的状态联系起来理解)

②所有问题都只需要解决一次(解决一次就是只需要由后面所说的状态转移方程解决即可)

前这两个特点可以看出,其实动态规划就是以对解答问题的每个步骤具化成状态,用通过状态与状态之间的递推关系写出的状态转移方程来解决实际问题的算法

③储存子问题的解(状态转移方程中往大问题转移一定需要子问题的解,所有需要将子问题的解储存起来)

2.要素

①状态的定义

②状态间的转移方程定义

③状态的初始化

(初始状态确定已知)

④返回结果

(返回的结果恰好完全符合题目要求)

3.用动态规划解题步骤

①根据题目所给条件,以及所问问题,初步判断是否具有动态规划的特点(可分治,可转移,可储存)

②对状态做出定义后判断当前状态可以由哪几种子状态通过哪几种方式(紧扣题目条件)得到,并以此为依据写出状态转移方程,并找全四个要素

③写代码

4.例题

题目

跳台阶扩展问题
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法

分析

所以要想跳到第n个台阶,我们可以从第1个台阶跳上来,也可以从第2个台阶跳上来……,很明显有小问题推大问题的情节
递推公式是
f(n)=f(n-1)+f(n-2)+……+f(2)+f(1);
同样如果我们想跳到第n-1个台阶,也可以列出下面这个公式
f(n-1)=f(n-2)+……+f(2)+f(1);
通过这两个公式我们可以得出
f(n)=2*f(n-1)
实际上他是个等比数列,base case当n等于1的时候结果为1,来看下代码

代码

class Solution {
public:
    int jumpFloorII(int number) 
    {
        if(number==0||number==1)
        {
            return number;
        }
        else
        {
            int ret=1;
            while(number>1)
            {
                ret=ret*2;
                number--;
            }
            return ret;
        }
    }
};

题目

最大连续子数组和
输入一个整形数组(可能有正数和负数),求数组中连续子数组(最少有一个元素)的最大和。要求时间复杂度为O(n)

分析

先假设以索引i-1结束时为状态,那么这个状态下时最大和怎么推导索引i结束时最大和呢,逻辑思考后可以发现,真实的最大连续子数组和肯定以某个索引结束的,所以找到dp中最大值即可。填充dp时,如果dp[i-1] < 0,那么dp[i]直接等于第i个数nums[i],否则就是dp[i] = dp[i-1] + nums[i]。

代码

 int main () {
    int n = 0, temp = 0;
    cin >> n;
    vector<int>  nums, dp(n, 0);
    while (cin >> temp) nums.push_back(temp);
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        if (dp[i-1] < 0) dp[i] = nums[i];
        else dp[i] = dp[i-1] + nums[i];
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}

题目

单词拆分
给定一个字符串和一个字符串数组,在字符串的任意位置拆分任意次后得到的字符串集合是否是给定字符串数组的子集。

分析

出发点:给定字符串s的每个字符i
最优解:对于每个i之前的字符序列,分为j(0<=j<=i)前面的序列和j后面的序列,求解i转化为求解j和i-j
状态d(i):i之前的字符序列分段后的字符串能不能在字典中找到
递推公式:d(i) = d(i)||(d(j)&sub(i-j)), 其中j=0~i

代码

#include
using namespace std;
class Solution {
public:
    bool wordBreak(string s, unordered_set &dict) {
        // 动态规划:1\. 每一个状态和前一个状态有关;2\. 最小子状态是可以求得的
        // 转移方程:f(i)表示s[0,i]可以分词,那么f(i) = f(j) && f(j+1, i); (0<=j<i)
        int len = s.length();
        vector dp(len+1, false);
        dp[0] = true;
        for (int i = 1; i <= len; ++i) {        // 注意终止条件,此处从1开始,终止条件应该为len
            for (int j = i-1; j >= 0; --j) {
                if (dp[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
};

~感谢观看❥(^_-)

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

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

相关文章

【Linux】软件包管理器 yum

什么是软件包和软件包管理器 在 Linux 下需要安装软件时&#xff0c; 最原始的办法就是下载到程序的源代码&#xff0c; 进行编译得到可执行程序。但是这样太麻烦了&#xff0c;所以有些人就把一些常用的软件提前编译好, 做成软件包 ( 就相当于windows上的软件安装程序)放在服…

Spring框架中IOC和DI详解

Spring框架学习一—IOC和DI 来源黑马Spring课程&#xff0c;觉得挺好的 目录 文章目录Spring框架学习一---IOC和DI目录学习目标第一章 Spring概述1、为什么要学习spring&#xff1f;2、Spring概述【了解】【1】Spring是什么【2】Spring发展历程【3】Spring优势【4】Spring体系…

java线程之Thread类的基本用法

Thread类的基本用法1. Thread类的构造方法2. Thread的几个常见属性常见属性线程中断等待一个线程小鱼在上一篇博客详细的讲解了如何创建线程,java使用Thread类来创建多线程,但是对于好多没有相关经验的人来说,比较不容易理解的地方在于操作系统调度的执行过程. 我们通过下面代码…

Tomcat部署及优化

目录 1.Tomcat概述 1.Tomcat的概念 2、Tomcat的核心组件 3.Java Servlet 的概念 4.JSP的概念 5.Tomcat中最顶层的容器------server 6.四个子容器的作用 7.Tomcat请求过程 2.Tomcat服务部署 1.Tomcat服务部署的步骤 2.实例操作&#xff1a;Tomcat服务部署 3.Tomcat 虚拟主机配置…

数据清洗是清洗什么?

在搭建数据中台、数据仓库或者做数据分析之前&#xff0c;首要的工作重点就是做数据清洗&#xff0c;否则会影响到后续对数据的分析利用。那么数据清洗到底是做什么事情呢&#xff1f;今天我就来跟大家分享一下。 数据清洗的基本概念 按百度百科给出的解释&#xff0c;“数据清…

Java之链表(不带头结点,带头结点,迭代实现,递归实现)

目录 一.链表 1.什么是链表 2.链表的分类 二.不带头结点单向链表的非递归实现 1.接口的定义 2. 不带头结点单向链表的结构 3.链表的添加操作(头插法和尾插法) 1.头插法 2.尾插法 4. 链表的插入操作 5.链表的删除操作 1.删除指定索引的结点 2.删除指定值的第一个结点…

一文带你领略 WPA3-SAE 的 “安全感”

引入 WPA3-SAE也是针对四次握手的协议。 四次握手是 AP &#xff08;authenticator&#xff09; 和 &#xff08;supplicant&#xff09;进行四次信息交互&#xff0c;生成一个用于加密无线数据的秘钥。 这个过程发生在 WIFI 连接 的 过程。 为了更好的阐述 WPA3-SAE 的作用 …

Thread的小补丁

Thread小补丁线程状态NewRunnableWaitingTimed_waitingBlocked线程安全线程的抢占式执行同时对同一个变量进行修改指令重排序操作不是原子的解决方案万恶之源优化我们自己的代码Synchronized和Volatile上一篇博客中,我们简单介绍了线程Thread的一些知识,一些基本的使用,但是单单…

数据结构和算法(1):数组

目录概述动态数组二维数组局部性原理越界检查概述 定义 在计算机科学中&#xff0c;数组是由一组元素&#xff08;值或变量&#xff09;组成的数据结构&#xff0c;每个元素有至少一个索引或键来标识 In computer science, an array is a data structure consisting of a col…

文心一言发布,你怎么看?chatGPT

百度全新一代知识增强大语言模型“文心一言”于2021年3月16日正式发布&#xff0c;作为一款自然语言处理技术&#xff0c;它引起了广泛的关注和讨论。 首先&#xff0c;文心一言是一款具有重大意义的自然语言处理技术。在人工智能领域&#xff0c;自然语言处理技术一直是一个难…

PyTorch 之 神经网络 Mnist 分类任务

文章目录一、Mnist 分类任务简介二、Mnist 数据集的读取三、 Mnist 分类任务实现1. 标签和简单网络架构2. 具体代码实现四、使用 TensorDataset 和 DataLoader 简化本文参加新星计划人工智能(Pytorch)赛道&#xff1a;https://bbs.csdn.net/topics/613989052 一、Mnist 分类任…

Lambda表达式

第一章 Java为什么引入 Lmabda表达式目的尽可能轻量级的将代码封装为数据1.1 什么是Lambda表达式Lambda表达式也被成为箭头函数、匿名函数、闭包 Lambda表达式体现的是轻量级函数式编程思想 ‘->’符号是Lambda表达式的核心符号&#xff0c;符号左侧是操作参数&#xff0c;符…

YOLOv8 多目标跟踪

文章大纲 简介环境搭建代码样例跟踪原理代码分析原始老版实现新版本封装代码实现追踪与计数奇奇怪怪错误汇总lap 安装过程报错推理过程报错参考文献与学习路径简介 使用yolov8 做多目标跟踪 文档地址: https://docs.ultralytics.com/modes/track/https://github.com/ultralyt…

【多线程】多线程案例

✨个人主页&#xff1a;bit me&#x1f447; ✨当前专栏&#xff1a;Java EE初阶&#x1f447; ✨每日一语&#xff1a;we can not judge the value of a moment until it becomes a memory. 目 录&#x1f35d;一. 单例模式&#x1f364;1. 饿汉模式实现&#x1f9aa;2. 懒汉模…

java如何创建线程

java如何创建线程1. java如何创建线程1.1 通过继承Thread类来创建线程1.2 通过实现Runnable接口来创建线程1.3 通过匿名内部类来创建线程1.4 lambda表达式1.5 通过实现Runnable接口的方式创建线程目标类的优缺点1. java如何创建线程 一个线程在Java中使用一个Thread实例来描述…

android8 rk3399 同时支持多个USB摄像头

文章目录一、前文二、CameraHal_Module.h三、CameraHal_Module.cpp四、编译&烧录Image五、App验证一、前文 Android系统默认支持2个摄像头&#xff0c;一个前置摄像头&#xff0c;一个后置摄像头需要支持数量更多的摄像头&#xff0c;得修改Android Hal层的代码 二、Camer…

VueX快速入门(适合后端,无脑入门!!!)

文章目录前言State和Mutations基础简化gettersMutationsActions&#xff08;异步&#xff09;Module总结前言 作为一个没啥前端基础&#xff08;就是那种跳过js直接学vue的那种。。。&#xff09;的后端选手。按照自己的思路总结了一下对VueX的理解。大佬勿喷qAq。 首先我们需要…

我的 System Verilog 学习记录(11)

引言 本文简单介绍 SystemVerilog 的其他程序结构。 前文链接&#xff1a; 我的 System Verilog 学习记录&#xff08;1&#xff09; 我的 System Verilog 学习记录&#xff08;2&#xff09; 我的 System Verilog 学习记录&#xff08;3&#xff09; 我的 System Verilo…

Linux lvm管理讲解及命令

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…

软件行业的最后十年【ChatGPT】

在这篇文章中&#xff0c;我将说明像 ChatGPT 这样的生成式人工智能 (GAI) 将如何在十年内取代软件工程师。 预测被离散化为 5 个阶段&#xff0c;总体轨迹趋向于完全接管。 但首先&#xff0c;一个简短的前言。 推荐&#xff1a;用 NSDT场景设计器 快速搭建3D场景。 1、关于AI…