20250104215643

思政课知识点

大题

第一章——第二节 正确的人生观

一. 高尚的人生追求

​ 把自己的人生目的与国家前途,民族命运,人民幸福联系在一起。

​ 新时代大学生要把为国家和人民事业无私奉献作为人生的最高追求,在服务人民,奉献社会中收获成长和进 步。

​ 只有确立了服务人民的,奉献社会的人生追求,才能正确掌握人生价值,培养高洁的操行和纯朴的情感,成 为一个高尚的人。

二. 积极进取的人生态度

​ 保持认真务实,乐观向上,积极进取的人生态度。

​ 大学生要学会对自己负责,对周围的人负责,对民族,国家,社会负责,做有担当,负责任的人。

​ 人生当务实,人生应乐观,人生要进取。

三. 人生价值的评价与实现

(一)正确评价人生价值

​ 既要看贡献的大小,也要看尽力的程度。

​ 既要尊重物质贡献,也要尊重精神贡献。

​ 既要注重社会贡献,也要注重自身完善。

(二) 人生价值的实现条件

​ 实现人生价值要从社会客观条件出发。

​ 实现人生价值要从个体自身条件出发。

​ 充分发挥主观能动性。


第三章——第二节 做新时代的忠诚爱国者

一. 坚持爱党爱国爱社会主义相统一

​ 当代中国,爱国主义的本质就是坚持爱党爱国爱社会主义高度统一。

​ “国”是中国共产党领导的社会主义中国。

​ 爱党爱国爱社会主义统一于实现中华民族伟大复兴的历史进程。

​ 爱国不能停留在口号上,要把理想与祖国和民族未来联系在一起,要以实际行动体现爱党爱国爱社会主义。

二. 维护祖国统一和民族团结

​ 国家统一和民族团结是中华民族根本利益所在。

(一) 维护和推进祖国统一

​ 推进祖国统一,必须保持香港,澳门,长期繁荣稳定,坚持贯彻一国两制,港人治港,澳人治澳的方针

​ 解决台湾问题,实现祖国完全统一,是党矢志不渝的历史任务,是实现中华民族伟大复兴的必然要求。

​ 要坚持一个中国原则和九二共识整个政治基础,和平统一,一国两制是实现两岸统一的最佳方式。

(二) 促进民族团结

​ 新时代大学生要像爱护自己的眼睛一样维护民族团结,像爱护自己的生命一样维护社会稳定,做民族团 结进步事业的建设者,维护者,促进者。

​ 要牢固树立正确的祖国观,民族观,文化观,历史观。

三. 尊重和传承中华民族历史文化

(一) 历史文化是民族生生不息的丰厚滋养

​ 中华优秀传统文化是中华民族的精神命脉,是中华民族得以延续的文化基因。

​ 我们必须尊重和传承中华民族历史文化,以时代精神激活中华优秀传统文化的生命力,不断推进中华优 秀传统文化创造性转化和创新性发展。

​ 历史是一面镜子,一位智者,最好的教科书,最好的清醒剂,最好的营养剂。

(二) 旗帜鲜明反对历史虚无主义

​ 祖国是人民最坚实的依靠,英雄是民族最闪亮的坐标。

​ 我们要对中华民族的英雄心怀崇敬,自觉传承好中华民族辉煌灿烂的历史文化。

​ 新时代大学生要树立大历史观和正确党史观,准确把握党的历史发展的主题主线,主流本质,深刻领悟 中国共产党为什么能,马克思主义为什么行,中国特色社会主义为什么好的历史逻辑,理论逻辑,实践 逻辑,真正理解历史,把握历史,增强历史自觉和历史自信。

四. 坚持立足中国又面向世界

弘扬新时代的爱国主义,既要尊重各国历史特点,文化传统,又要积极倡导求同存异,相互借鉴,共同进步。

(一) 维护国家发展主体性

​ 党的百年奋斗成功道路是党领导人民独立自主探索开辟出来的,马克思主义的中国篇章是中国共产党人 依靠自身力量实践出来的,贯穿其中的一个基本点就是从中国的基本国情出发。

​ 新形势下,要坚持独立自主,自力更生,既虚心学习,又坚定民族自尊心和自信心,把中国发展进步的 命运牢牢握在自己手里。

(二) 自觉维护国家安全

​ 国家安全是民族复兴的根基,社会稳定是国家强盛的前提。

​ 确立总体国家安全观。

​ 增强国防意识,履行维护国家安全的义务。

(三) 推动构建人类命运共同体

​ 没有哪个国家能够独自应对人类面临的各种挑战,也没有哪个国家能够退回到自我封闭的孤岛。

​ 构建人类命运共同体是世界各国人民前途所在。


第四章——第二节 社会主义核心价值观的显著特征

一. 反映人类社会发展进步的价值理念

社会主义核心价值观具有超越以往一切社会核心价值观的先进性。

(一) 体现社会主义的本质属性

​ 社会主义核心价值观的先进性。集中体现在它是社会主义所坚持和追求的价值理念。

​ 社会主义核心价值观遵循着人类历史发展的轨迹。作为社会意识的价值观念是社会存在的反映。

​ 社会主义作为人类社会迄今为止最先进的社会制度,其价值观同社会主义经济基础和上层建筑相适应, 充分彰显了社会主义社会的本质要求。

​ 中国走上社会主义道路,是近代以来中国社会发展的历史必然,是历史的选择,人民的选择。

​ 社会主义核心价值观生成于中国特色社会主义建设实践,同当今中国最鲜明的时代主题相适应,是中国 特色社会主义本质规定的价值表达。

(二) 扎根中华优秀传统文化土壤

​ 源远流长的中华优秀传统文化,是中华民族发展壮大的独特优势,也是社会主义核心价值观历史底蕴的 集中体现。

​ 中华优秀传统文化是涵养社会主义核心价值观的重要源泉。

​ 培育和弘扬社会主义核心价值观,必须从中华优秀传统文化中汲取丰富营养,深入中华民族历久弥新的 精神世界。推动中华优秀传统文化创造性转化和创新性发展。

(三) 吸纳世界文明有益成果

​ 社会主义核心价值观吸纳了世界文明的有益成果。

​ 社会主义核心价值观在吸收人类优秀价值理念的基础上,以中国经验,中国实践为民主,自由,平等, 公正,法治等价值理念赋予社会主义性质,代表了人类社会前进的方向和价值理念。

二. 彰显人民至上的价值立场

社会主义核心价值观坚持人民历史主体地位,代表最广大人民的根本利益,反映最广大人民的价值诉求,引导最广大人民为实现美好社会理想而奋斗。

人民性是社会主义核心价值观的根本特性。

(一) 尊重人民群众历史主体地位

​ 马克思主义唯物史观指出人民群众在社会历史发展中的主体作用,认为人民群众是历史的创造者。

​ 人民是中国共产党执政的最深厚基础和最大底气,人民至上是社会主义核心价值观鲜明的价值立场。

(二) 体现以人民为中心的价值导向

​ 为中国人民谋幸福,为中华民族谋复兴,是中国共产党人的初心和使命,也是党领导现代化建设的出发 点和落脚点。

​ 中国共产党坚持人民是历史的创造者的观点,践行全心全意为人民服务的根本宗旨,坚持人民当家作 主,坚持以人民为中心的发展思想,把人民对美好生活的向往作为奋斗目标。

​ 以人民为中心的发展思想,要体现在经济社会发展的各个环节。

​ 在经济建设上,共同富裕;在政治建设上,人民当家作主;在文化建设上,人民是文化事业的主体;在 社会发展上,保障和改善民生;在生态文明建设上,人与自然和谐共生。

三. 因真实可信而具有强大的道义力量

(一) 社会主义核心价值观是真实可信的

​ 中国特色社会主义民主更注重内容和结果,不仅有选举民主,还有协商民主,基层民主,保证人民依法 实行民主选举,民主协商,民主决策,民主管理,民主监督。

(二) 认清西方“普世价值”的实质

​ “普世价值”是一种极具迷惑性,欺骗性并且带有鲜明政治倾向的价值观。

​ “普世价值”在理论上的虚伪性:西方国家所谓的“普世价值”并非指人类道德评价,审美评价的普遍性或共 性,而是特指资本主义价值观,从根本上来说,是为资产阶级利益服务的。

​ “普世价值”在实践上的虚伪性:balabala;

坚定价值观自信,要自觉以社会主义核心价值观为引领,运用马克思主义客观辩证地分析各种错误价值观的实质,不断增强社会凝聚力和价值共识。


第五章——第二节 吸收借鉴优秀道德成果

一. 传承中华传统美德

中华传统美德是人类文明发展地重要精神财富,是社会主义道德建设的源头活水。

(一) 中华传统美德的基本精神

​ 重视整体利益,强调责任奉献。始终强调整体利益,国家利益和民族利益的重要性。

​ 推崇仁爱原则,注重以和为贵。推崇仁爱,崇尚和谐是中华民族的优良传统和高尚品德。

​ 注重人伦关系,重视道德义务。非常重视每个人在人伦关系中的地位及其价值。

​ 追求精神境界,向往理想人格。把道德理想的实现看作人生诸种需要中最高层次的需要。

​ 强调道德修养,注重道德践履。要使社会的道德原则和规范转换为自身的思想品德和行为实践。

(二) 中华传统美德的创造性转化和创新性发展

​ 传统道德是一个矛盾体,具有鲜明的两重性。我们要坚定历史自信,文化自信,不忘本来,辨证取舍, 古为今用,推陈出新,传承和弘扬中华传统美德。

​ 加强对中华传统美德的挖掘和阐发。

​ 用中华传统美德滋养社会主义道德建设。

​ 在对待传统道德的问题上,要反对两种错误思潮,“复古论”和“虚无论”。

​ 我们要树立高度的文化自觉和文化自信,深入挖掘中华优秀传统文化蕴含的思想观念,人文精神,道德 规范,结合时代要求继承创新,让中华文化展现出永久美丽和时代风采。

二. 发扬中国革命道德

中国革命道德是对中华传统美德的延续和发展。传承和发扬中国革命道德,是弘扬中华传统美德的应有之义,是加强社会主义道德建设的客观需要,也是激励大学生锤炼优良道德品质的必然要求。

(一) 中国革命道德的形成与发展

​ 中国革命道德,是指中国共产党人,人民军队,一切先进分子和人民群众在中国革命,建设,改革中所 形成的优秀道德,是马克思主义与中国革命,建设,改革的伟大实践相结合的产物,是中华民族极其宝 贵的道德财富。

​ 中国共产党始终高度重视继承和发扬革命道德传统。我们要深刻认识到红色政权来之不易,新中国来之 不易,中国特色社会主义来之不易。

​ 中国革命道德作为一种精神力量对中国的革命,建设,改革事业发挥着极其重要的作用。

​ 弘扬中国革命道德,要同弘扬中华传统美德相结合。

​ 中国革命道德继承了中国传统道德的精华,摒弃了传统道德的糟粕,是中国优良传统道德的延续和发 展,是超越了中华传统美德的时代局限而形成的一种崭新的道德。

(二) 中国革命道德的主要内容

​ 为实现社会主义和共产主义的理想而奋斗。列宁指出:”为巩固和完成共产主义事业而斗争,这就是共产 主义道德的基础。“ 坚持社会主义和共产主义理想信念是革命道德的灵魂。

​ 全心全意为人民服务。中国革命道德强调要为群众服务,为大众谋幸福,为人民利益献身,这是对一切 革命人士和先进分子的要求。

​ 始终把革命利益放在首位。”以革命利益为第一生命,以个人利益服从革命利益“。

​ 树立社会新风,建立新型人际关系。

​ 修身自律,保持节操。以中国革命事业为重,严于律己,淡泊名利。

(三) 中国革命道德的当代价值

​ 中国革命道德是中国共产党领导全体人民实现民族独立,人民解放的精神支撑,对于我们走好新时代的 长征路,实现中华民族伟大复兴仍然具有极其重要的现实意义。

​ 有利于加强和巩固社会主义和共产主义的理想信念。弘扬中国革命道德,有利于树立和培养人民群众的 社会主义和共产主义的理想信念,有利于坚持和发展中国特色社会主义道路。

​ 有利于培育和践行社会主义核心价值观。中国革命道德是先进价值观在道德领域的集中体现,蕴含着培 育和践行社会主义核心价值观的丰富思想道德资源。

​ 有利于引导人们树立正确的道德观。

​ 有利于培育良好的社会道德风尚。要充分发挥革命道德的精神力量,培育良好的社会道德风尚,净化社 会人际关系,抵制各种腐朽思想,树立浩然正气,凝聚崇德向善的正能量。

​ 大学生发扬革命道德,就要深入了解革命历史,体会革命道德的本质内涵,历史意义和当代价值,努力 在坚持和发展中国特色社会主义伟大进程中创造无愧于时代,无愧于人民,无愧于先辈的业绩。

三. 借鉴人类文明优秀道德成果

​ 一种文化能够通过与其他文化交流碰撞和冲突融合而保持其生命力,是实现自我更新和自我发展的重要条 件。

​ 从道德形成和发展的过程来看,道德都是某个民族或国家在特定历史条件下,为回应来自自然环境,社 会生活和人际关系的各种矛盾而形成和发展起来的,反映了具体民族或国家的生存方式和生活态度。

​ 借鉴和吸收人类文明优秀道德成果,必须秉承正确的态度和科学的方法。要坚持马克思主义立场,观 点,方法,在道德问题上把握好共性和个性,抽象和具体,一般和个别的关系。要坚持以我为主,为我 所用,批判吸收其他国家的道德成果。

​ 当今世界,各国人民形成了你中有我,我中有你的命运共同体。

​ 人类文明优秀道德成果是由世界各国各民族共同创造的,中华民族的优良道德传统和其他各国的优良道 德传统都是其重要组成部分。

第六章——第四节 自觉尊法学法守法用法

大学生是未来国家建设的中坚力量,要积极培养法治思维,正确理解依法行使权利和履行义务,不断提升法治素养,自觉尊法学法守法用法,成为社会主义法治的忠实崇尚者,自觉遵守者,坚定捍卫者。

一. 培养社会主义法治思维

(一) 法治思维及其内涵

​ 法治思维是指以法治价值和法治精神为导向,运用法律原则,法律规则,法律方法思考和处理问题的思 维模式。

​ 法治思维包含以下几层含义:

​ 一. 法治思维以法治价值和法治精神为指导,蕴含着公平,平等,民主,人权等法治理念,是一种正当性 思维。

​ 二. 法治思维以法律原则和法律规则为依据指导人们的社会行为,是一种规范思维。

​ 三. 法治思维以法律手段与法律方法为依托分析问题,处理问题,解决纠纷,是一种逻辑思维。

​ 四. 法治思维是一种符合规律,尊重事实的科学思维。

​ 法治思维是基于对法律的尊崇和对法治的新年判断是非,权衡利弊,解决问题的思维方式。

(二) 法治思维的基本内容

​ 法治思维主要表现为价值取向和规则意识两个方面。

​ 一般来讲,法治思维主要包括法律至上,权力制约,公平正义,权利保障,程序正当等内容。

​ 法律至上:是指在国家或社会的所有规范中,法律是地位最高,效力最广,强制力最大的规范。

​ 法律至上尤其指宪法至上,因为宪法具有最高的法律效力,是其他一切法律的依据。

​ 法律至上表现为法律的普遍使用,优先适用和不可违反。

​ 法律的普遍适用,是指法律在本国主权范围内对所有人具有普遍的约束力。

​ 权力制约:是指国家机关的权力必须受到法律的规制和约束。

​ 在我国,国家权力是人民的,即一切权力为民所用;国家权力是为人民服务的,即一切权力为 民所用。

​ 权力制约包括权力由法定,有权必有责,用权受监督,违法受追究四项要求。

​ 公平正义:是指社会的政治利益,经济利益和其他利益在全体社会成员之间合理,公平分配和占有。

​ 一般来讲,公平正义主要包括权利公平,机会公平,规则公平和救济公平。

​ 权利公平又包括:权利主体平等,享有的权利特别是基本权利平等,权利保护和权利救济平 等。

​ 机会公平包括:国家和社会要为社会成员创造平等的起点,社会成员的发展进步权要受到同等 尊重,不断拓展社会成员的发展领域,不仅要关注当代人,还要考虑后代人的机会平等。

​ 规则公平:是指对所有人适用同一规则和标准,不得因人而异。包括法律规则面前人人平等, 法律内容面前人人平等和法律保护面前人人平等,任何人不得享有法律之外的特权,任何人也 不会被法律排除在保护之外。

​ 救济公平:是指为权利受到侵害或处于弱势地位的公民提供平等有效的救济,包括司法救济公 平,行政救济公平,社会救济公平。

​ 权利保障:主要是指对公民权利的法律保障,具体包括公民权利的宪法保障,立法保障,行政保障和司 法保障。

​ 宪法保障是权利保障的前提和基础。

​ 立法保障是权利保障的重要条件。

​ 行政保障是权利保障的关键环节。

​ 司法保障是公民权利保障的最后防线。

​ 程序正当:程序法包括民事诉讼,刑事诉讼,行政诉讼和仲裁等方面的法律。

​ 程序的正当,表现在程序的合法性,中立性,参与性,公开性,时限性等方面。

二. 依法行使权利与履行义务

(一) 法律权利与法律义务

​ 权利和义务关系是社会关系的法律表现。权利和义务中被法律规定和认可的,称为法律权利和法律义 务。

​ 享有法律权利的主体称为权利人,承担法律义务的主体称为义务人。

​ 法律权利:是指由一定的社会物质生活条件所制约的行为自由,是法律所允许的权利人为了满足自己的 利益而采取的,由其他人的法律义务所保障的法律手段。

​ 强调社会的物质生活条件对权利的制约和决定作用,这是马克思主义权力观和其他权力观的根 本区别。

​ 法律权利具有以下四个特征:一是实现程度受社会物质生活条件的制约。

​ 二是因社会制度和国家法律的不同而存在差异。

​ 三是法律权利具有不可侵犯性。

​ 四是法律权利必须依法行使。

​ 法律义务:是指由一定的社会物质生活条件所制约的社会责任。

​ 法律义务的履行表现为作为和不作为两种形式。

​ 法律义务具有以下四个特点:一是法律义务是历史的,随社会发展不断调整和变化。

​ 二是法律义务源于现实需要。

​ 三是法律义务必须依法设定。

​ 四是法律义务可能发生变化。

​ 法律权利和法律义务不可分割,相互依存。

​ 每个人既是享受法律权利的主体,又是承担法律义务的主体。

​ 在法治国家,不存在只享受权力的主体,也不存在只承担义务的主体。

​ 大学生应当正确把握依法行使权利,履行义务的基本要求,既珍惜自己权利又尊重他人权利,既善于行 使权利又自觉履行义务。

(二) 我国宪法法律规定的权利

​ 依法行使法律权利,是体现权利正当性和保障权利实现的充分必要条件。

​ 宪法法律规定公民享有的一系列权利,主要包括政治权利,宗教信仰自由,人身权利,财产权利,社会 经济权利及文化教育权利等。

​ 政治权利,是公民参与国家政治活动的权利和自由的统称,它的行使主要表现为公民参与国家,社会租 住和管理的活动。

​ 政治权利主要包括以下四方面内容:

​ 选举权,表达权,民主管理权,监督权。

​ 宗教信仰自由,是指公民依据内心的信念,自由地信仰宗教的自由。

​ 具体内容包括信仰宗教的自由,从事宗教活动的自由,举行或参加宗教仪式的自由等。

​ 人身权利,是指公民的人身不受非法侵犯的权利,它是公民参加国家政治,经济与社会生活的基础。

​ 具体内容包括以下五方面内容:

​ 生命健康权,人身自由权,人格尊严权,住宅安全权,通信自由权

​ 财产权利,是指公民,法人或其他组织通过劳动或其他合法权利取得财产和占有,使用,收益,处分财 产的权利。

​ 具体内容包括以下两方面:

​ 私有财产权,继承权

​ 社会经济权力,是指公民要求国家根据社会经济的发展状况,积极采取措施干预社会经济生活,加强社 会建设,提供社会服务,以促进公民的自由和幸福,保障公民过上健康而有尊严的生活的权利。

​ 具体内容包括以下四方面:

​ 劳动权,休息权,社会保障权,物质帮助权

​ 文化教育权利,是公民按照宪法的规定在文化和教育领域享有的权利,主要包括教育方面的权利和文化 活动方面的权利。

​ 教育方面的权利主要表现为受教育权。

​ 文化活动方面的权利主要表现为公民的文化权利。

(三) 依法行使法律权利

​ 权利行使目的的正当性。公民在行使法律权利时,不仅要在形式上符合相关法律的规定,也要符合立法 意图和精神。

​ 权利行使方式的法定性。权利行使的方式分为口头方式,书面方式和行为方式,有时口头方式和书面方 式可以兼用。

​ 权利行使的正当程序,

(四) 依法履行法律义务

​ 义务法定,一方面是说义务的设定必须有法律依据,另一方面是说法定的义务应当履行。

​ 维护国家统一和民族团结的义务。维护国家统一是整个社会共同体存在和发展的基础,也是以宪法为核 心的整个法律制度存在的基础。同时,国家统一也是公民实现法律权利与自由的前提。

​ 遵守宪法和法律的义务。

​ 具体包含以下五个方面:

​ 保守国家秘密,爱护公共财产,遵守劳动纪律,遵守公共秩序,尊重社会公德。

​ 维护祖国安全,荣誉和利益的义务。

​ 国家安全是指国家的领土完整和主权不受侵犯,国家政权不受威胁。

​ 国家安全是国家政权稳定和公民依法行使权利与自由的根本保障。

​ 国家荣誉是指国家的声誉和尊严。

​ 维护国家荣誉是指维护国家的声誉和尊严不受损害,对有辱祖国荣誉,损害祖国利益的行为给予法 律制裁。

​ 国家利益分为对外和对内。

​ 对外主要是指民族的政治,经济,文化等方面的权利和利益

​ 对内主要是指公共利益。

​ 依法服兵役的义务。

三. 不断提升法治素养

(一) 尊重法律权威

​ 法律通过调整社会关系,规范人的行为,保障社会成员的利益,实现稳定合理的社会秩序。

​ 法律的权威源自人民的内心拥护和真诚信仰。

​ 人民权益要靠法律保障,法律权威要靠人民维护。

​ 人民是国家的主人,是法治国家的建设者和捍卫者,尊重法律权威是其法定义务和必备素质。

​ 尊重法律权威,就要信仰法律,遵守法律,服从法律,维护法律。

(二) 学习法律知识

​ 学习和掌握基本的法律知识,是提升法治素养的前提。

​ 参与法治实践是学习法律知识的有效途径。

​ 参与法治实践的方式和途径有以下三个:

​ 参与立法讨论,旁听司法审判,参与校园法治文化活动。

(三) 养成守法习惯

​ 增强规则意识。养成规则意识,坚持守法守规是每一个法治国家公民的基本素养。

​ 守住法律底。

(四) 提高用法能力

​ 维护自身权利,大学生要增强权利意识,用法处理纠纷,依法维护权。

​ 维护社会利益,大学生要遵法守规,遇事找法,善于用法,做新时代的守法人,护法人。

做了一点dp后的总结

算法日志-1

这几天间间断断地在Leetcode上面写了一二十道DP,主要是:

爬楼梯
打家劫舍
网格图

虽然说没做太多,但是也算是有了一点感觉(其实还是菜,做不出来


爬楼梯

对于爬楼梯问题其实没什么好讲的,本质上和DFS很像,只不过一个是递,一个是归,这种情况下基本就是DP/DFS+记忆化搜索。


打家劫舍

打家劫舍分为两类,一种是下标相邻有关,一种是值域相邻有关,下标类的相对好写,只需要找出单方向的递推简化过程,转化为状态转移方程,一步步求解就好。而值域相邻有关可以使用collections.Counter生成包含 元素->次数 的字典,将最大值+1作为len(dp),同时初始化dp[i]为 元素大小*次数,转化为下标相邻有关问题.

删除并获得点数


给你一个整数数组 nums ,你可以对它进行一些操作。

每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除 所有 等于 nums[i] - 1nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
Example:
输入:nums = [3,4,2]
输出:6
解释:
删除 4 获得 4 个点数,因此 3 也被删除。
之后,删除 2 获得 2 个点数。总共获得 6 个点数。

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 104

题解:

1
2
3
4
5
6
7
8
9
10
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
cnt=Counter(nums)
max_val=max(cnt.keys())
dp=[0] * (max_val+1)
for i , j in cnt.items():
dp[i] = i * j
for i in range(1 , max_val+1):
dp[i]=max(dp[i-1] , (dp[i-2] if i>=2 else 0) + dp[i])
return dp[-1]


网格图

然后是网格图DP,网格图DP其实是抽象二维DP的铺垫(背包,最长公共子序列),这里以Leetcode 1289.下降路径最小和II为

下降路径最小和 II


给你一个 n x n 整数矩阵 grid ,请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为:从 grid 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。

示例 1:

输入:grid = [[1,2,3],[4,5,6],[7,8,9]]
输出:13
解释:
所有非零偏移下降路径包括:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ,所以答案是 13 。

示例 2:

输入:grid = [[7]]
输出:7

提示:

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • -99 <= grid[i][j] <= 99

这题最直观的想法就是找每一行的最小值,然后一路加到底,但是题目要求是非零偏移下降路径,因此要分为两种情况:

  1. 与上一行最小值对齐,即 cur_index=pre_row.index(min)此时不能取最小值,只能寻求上一行的次小值(第二小的值)。
  2. 不与上一行最小值对齐,cur_index!=pre_row.index(min)直接取最小值。

因此对于每一行,需要找出最小的两个值,对于需要找出可迭代对象多个最小值/最大值的场景,考虑使用heapq模块里的nsmallest / nlargest(n,iterable)
接下来只需要迭代每一行的时候,选择+=哪一个最小值就行。

代码:

1
2
3
4
5
6
7
class Solution:
def minFallingPathSum(self, grid: List[List[int]]) -> int:
for pre_row,cur_row in pairwise(grid):
min_two=nsmallest(2,pre_row)
for i,pre in enumerate(pre_row):
cur_row[i]+=min_two[0] if pre!=min_two[0] else min_two[1]
return min(grid[-1])

其中pairwise用来挨个迭代相邻的两个元素,也即:(row[0],row[1]),(row[1],row[2])…

总结下来,DP的思想很像DFS,编写的前提都是我假设前面的已经取到了所需要的值,首先要分析题目属于DP问题当中的哪一种题型,如果不够直接则思考如何转换,然后找出状态转移方程,处理边界条件(使用哨兵),最后处理数组得到答案。

感想

归纳题型真的很重要,这个和高中数学有相似之处,Dalao做题都是一眼丁真,简单处理之后直接套框架,前期练习需要的就是对题型,框架的理解和把握程度。

有关勒让德定理的思考

前几天刷力扣遇到了一个考察阶乘性质的题

题目本身不难 可是要求O(logn)
很快想到可以将尾随0分解成2*5,如此一来题目就很清晰了
只需要找到有多少个2的倍数和5的倍数就行


根据次幂计数

很容易想到统计2^n^和5^n^各出现了多少次,对应加n,然后取两个和较小的那个
题中n<=10000,代码可以这么写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a=[5,25,125,625,3125]
b=[2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
suma=sumb=0
for i in range(n+1):
for j in range(4):
if i>=a[j] and i<a[j+1]:
suma+=j+1
if i>=a[4]:
suma+=5
for i in range(n+1):
for j in range(12):
if i>=b[j] and i<b[j+1]:
sumb+=j+1
if i>=b[12]:
sumb+=13
return min(suma,sumb)

这么写很直观,但是判断上太麻烦,能不能只要有i>a[j]就计数呢?

勒让德定理

这就该引出勒让德定理了:

直观来说就是将竖着的楼梯横着计数
于是乎代码就可以写成这样:

1
2
3
4
5
6
7
a=[5,25,125,625,3125]
b=[2,4,8,16,32,64,128,256,512,1024,2048,4096,8192]
for i in range(5):
a[i]=n//a[i]
for i in range(13):
b[i]=n//b[i]
return min(sum(a),sum(b))

进一步优化

看起来就简介多了,实际上这种形式已经能击败100%了
但是在思考阶乘中2和5出现的次数时不难发现,2的次数总少于5
于是干脆舍弃对2计数,可以再精简一些:

1
2
3
4
a=[5,25,125,625,3125]
for i in range(5):
a[i]=n//a[i]
return sum(a)

如此这道题从算法层面就圆满了

tips

这道题最佳写法如下:

1
2
3
4
5
ans = 0
while n:
n //= 5
ans += n
return ans

对空间做了进一步优化

二分法开闭区间写法异同

主要分为四类:(以二分查找为例)

1
2
3
4
5
6
7
8
left , right = 0 , n-1
while left <= right:
mid = (left + right)//2
if nums[mid]<target:
left = mid + 1
else:
right = mid - 1
return left

tips

可以看到主要区别就是left,right的初始值,和mid是否+-1,
可以很简单地理解为,开区间就是把一个边界向外扩大了1,也
即相对mid更远了,因此所有计数都相应地外扩1