代码随想录算法训练营 ---第五十七天

今天是两道动态规划的经典题目。

第一题:


简介:

做了今天的题目我有了新的理解,我觉得过去我过于注重对于二维数组的理解,忽略了对dp数组i  和 j 的含义的理解。

动态规划五部曲:

1.确定dp数组的含义

    本题我们将i 和 j 看作是 s字符串两端,所以我们将其定义为 i和j 之间的子串是否为回文子串。

有人会问为何我们不像往常一样,将dp含义定义为问题所问,是因为我们定义dp数组是为了找出其中的递推关系。帮助我们更好的解题。那么此时我们是不是能找到一种递归关系,也就是判断一个子字符串(字符串的下表范围[i,j])是否回文,依赖于,子字符串(下表范围[i + 1, j - 1])) 是否是回文。所以为了明确这种递归关系,我们的dp数组是要定义成一位二维dp数组。布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。

2.确定dp数组的递推公式

    两种情况 s[i] == s[j]                          

  • 情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
  • 情况二:下标i 与 j相差为1,例如aa,也是回文子串
  • 情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,我们看i到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j-1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

                   s[i] != s[j]   dp[i][j] = false

3.确定数组的初始化

     都初始化为false

4.确定遍历顺序

   怎么遍历要看我们的递推公式我们呢可以看出是从左下往右上推导 所以我们从上到下,从左到右遍历

5.打印数组

代码实现:

    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }

第二题:

简介:

本题相较于上题有所不同,首先上题是连续的子串,本题可以是不连续的。但是思路相差不大,都是将dp模型i 和 j 看作是 s字符串两端,但是我们将其定义为 i和j 之间的子串的长度。

动态规划五部曲:

1.确定dp数组的含义

   将dp模型i 和 j 看作是 s字符串两端,但是我们将其定义为 i和j 之间的子串的长度

2.确定dp数组的递推公式

    两种情况: s[i]== s[j]   相等的话我们看 i+1 和 j-1 之间的子串的长度加2 就是当前的长度

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

                       s[i]!= s[j]            

3.确定数组的初始化

    因为递推公式原因 我们可以看出 我们无法推到 i 和 j 相同的情况 所以我们将 i 和 j相同的情况初始化为1 因为 一个字符 子串长度为1.

其他初始化为零

4.确定遍历顺序

  

5.打印数组

代码实现: 

    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
        for(int i=0;i<s.size();i++)dp[i][i] = 1;
        for(int i=s.size()-1;i>=0;i--){
           for(int j=i+1;j<s.size();j++){
               if(s[i] == s[j]){
                   dp[i][j] = dp[i+1][j-1]+2;
               }else{
                   dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
               }
        }}
         return dp[0][s.size()-1];
    }

总结: 

动态规划有点折磨,有点抽象。一定要多刷几遍,多理解。继续加油!

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

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

相关文章

【Flutter】vs2022上开发flutter

在vs上开发flutter&#xff0c;结果扩展仓库上没办法找到Dart&#xff0c;Flutter。 在 这 搜索Dart时也无法找到插件。 最后发现是安装工具出错了 安装了 开发需要的是

Cython批量编译py文件并打包python项目为whl

1、Cython批量编译py文件 Cython是一个编程语言&#xff0c;它通过类似Python的语法来编写C扩展并可以被Python调用。能够将PythonC混合编码的.pyx脚本转换为C代码&#xff0c;主要用于优化Python脚本性能或Python调用C函数库。基于它的原理&#xff0c;可以得到一种代码加密的…

C++——红黑树

作者&#xff1a;几冬雪来 时间&#xff1a;2023年12月7日 内容&#xff1a;C——红黑树讲解 目录 前言&#xff1a; 红黑树的概念&#xff1a; 红黑树的性质&#xff1a; 红黑树的路径计算&#xff1a; 最长路径和最短路径&#xff1a; AVL树与红黑树的区别&#xff…

测试新手百科:Postman简介、安装、入门使用方法详细攻略!

一、Postman背景介绍 用户在开发或者调试网络程序或者是网页B/S模式的程序的时候是需要一些方法来跟踪网页请求的&#xff0c;用户可以使用一些网络的监视工具比如著名的Firebug等网页调试工具。今天给大家介绍的这款网页调试工具不仅可以调试简单的css、html、脚本等简单的网…

zabbix(2)

zabbix的自动发现机制 zabbx客户端主动和服务端联系&#xff0c;将自己的地址和端口发送服务端&#xff0c;实现自动添加监控主机 客户端是主动的一方 缺点&#xff1a;自定义网段中主机数量太多&#xff0c;登记耗时会很久&#xff0c;而且这个自动发现机制不是很稳定 zabb…

Python---面向对象的综合案例

案例1&#xff1a;定义学员信息类&#xff0c;包含姓名、成绩属性&#xff0c;定义成绩打印方法&#xff08;90分及以上显示优秀&#xff0c;80分及以上显示良好&#xff0c;70分及以上显示中等&#xff0c;60分及以上显示合格&#xff0c;60分以下显示不及格&#xff09; 学员…

easyexcel导出报错 java.lang.NoClassDefFoundError: org/apache/poi/POIXMLTypeLoader

报错&#xff1a; org.springframework.web.util.NestedServletException: Handler processing failed; nested exception is java.lang.NoClassDefFoundError: org/apache/poi/POIXMLTypeLoaderorg.springframework.web.servlet.DispatcherServlet.triggerAfterCompletionWit…

微信小程序-发消息

一、引言 作者开发《目的地到了》的时候需要给用户发消息&#xff0c;一开始用了消息模板&#xff0c;后面上真机才发现微信把这个给取消掉了。后面通知用户都是通过订阅消息 二、前端 调用wx的api&#xff0c;要把模板id传进去&#xff0c;如果用户没有点击过同意会弹出弹窗提…

多人群聊代码

服务端 import java.io.*; import java.net.*; import java.util.ArrayList; public class Server{public static ServerSocket server_socket;public static ArrayList<Socket> socketListnew ArrayList<Socket>(); public static void main(String []args){try{…

MTK平台如何debug A2DP 卡音问题

一 听auido文件 卡音问题首先要听以下3个部分的audio文件 1 .auido dump中的af_mixer_write_pcm_xxx.wav,这是auido传 给A2DP的源文件,如果这里有卡音,可以转给auido的人check • track是AudioTrack送到AudioFlinger的聲音 • mixer_pcm是AudioFlinger處理過程中的聲音 •…

Java多线程技术二:线程间通信——InheritableThreadLocal的使用

1 概述 使用InheritableThreadLocal可以在子线程中取得父线程继承下来的值。 2 ThreadLocal类不能实现值的继承 public class Tools {public static ThreadLocal t1 new ThreadLocal(); } public class ThreadA extends Thread{Overridepublic void run(){try {for (int i…

功能测试,接口测试,自动化测试,压力测试,性能测试,渗透测试,安全测试,具体是干嘛的?

软件测试是一个广义的概念&#xff0c;他包括了多领域的测试内容&#xff0c;比如&#xff0c;很多新手可能都听说&#xff1a;功能测试&#xff0c;接口测试&#xff0c;自动化测试&#xff0c;压力测试&#xff0c;性能测试&#xff0c;渗透测试&#xff0c;安全测试等&#…

【Python】流畅!一个非常好用的网络数据采集工具!

文章目录 前言一、注册二、初窥三 数据集四 自定义网站网络爬虫总结 前言 你是否曾为获取重要数据而感到困扰&#xff1f;是否因为数据封锁而无法获取所需信息&#xff1f;是否因为数据格式混乱而头疼&#xff1f;现在&#xff0c;所有这些问题都可以迎刃而解。让我为大家介绍…

2023年12月实时获取地图边界数据方法,省市区县街道多级联动【附实时geoJson数据下载】

首先&#xff0c;来看下效果图 在线体验地址&#xff1a;https://geojson.hxkj.vip&#xff0c;并提供实时geoJson数据文件下载 可下载的数据包含省级geojson行政边界数据、市级geojson行政边界数据、区/县级geojson行政边界数据、省市区县街道行政编码四级联动数据&#xff0…

docker的基本管理和概念

docker是什么&#xff1f; docker是开源的应用容器引擎。基于go语言开发的。运行在Linux系统中的开源的轻量级的“虚拟机”。 docker的容器技术可以在一台主机上轻松的为任何应用创建一个轻量级的、可移植的、自给自足的容器 docker的宿主机是linux系统。集装箱可以理解为相互…

Java简易版:UDP协议实现群聊

要先 运行服务端&#xff0c;在运行客户端&#xff0c;否则会报错。 服务端&#xff1a; package 二十一章;import java.io.*; import java.net.*; import java.util.ArrayList; public class T{public static ServerSocket server_socket;public static ArrayList<Socket…

EasyX图形化学习

1.EasyX是什么&#xff1f; 是基于Windows的图形编程&#xff0c;给用户提供函数接口&#xff0c;最终函数调用会由Windows的API实现。 注&#xff1a;EasyX只适配 c 。 2.头文件&#xff1a; <easyx.h>---只包含最新的函数 <graphics.h>---包含<easyx.h&g…

Vue3整合Element Plus过程

Vue 是一种流行的JavaScript框架&#xff0c;用于构建交互式和现代化的Web应用程序。Vue 3是Vue框架的最新版本&#xff0c;带来了新特性和改进。而Element Plus是一个基于Vue框架的UI组件库&#xff0c;它提供了丰富的UI组件和样式&#xff0c;能够帮助我们快速构建出漂亮且功…

Towards High-Quality and Efficient Video Super-Resolution via

code:coulsonlee/STDO-CVPR2023: [CVPR2023] Towards High-Quality and Efficient Video Super-Resolution via Spatial-Temporal Data Overfitting (github.com) 随着深度卷积神经网络&#xff08;DNN&#xff09;在计算机视觉的各个领域得到广泛应用&#xff0c;利用DNN的过…