动态规划零基础讲解

动态规划零基础讲解xx

2024年8月11日主要面向零基础的同学，简单梳理一下知识点，同时穿插部分例题因为动态规划种类比较多，所以穿插例题加深理解前半包括DP基础、序列DP、背包选讲、区间DP中间大约休息10分钟后半包括状压DP、树型DP、数位DP及一些常见优化DP思路，视剩余时间可能会多讲一些例题知识点比较基础，但是部分例题还是有一点挑战性欢迎大家互动本次课程的安排你的算法竞赛水平是（选择最高一档，高中大学都有获奖请选大学获奖）XCPC区域赛铜牌XCPC区域赛银牌XCPC区域赛金牌XCPC区域赛金牌不足以描述我的水平ABCD提交高中获得NOIP省二及以上E高中获得NOI银牌及以上F参加过算法竞赛，但没有获得过上述奖项G没有参加过算法竞赛H投票(匿名)最多可选1项是否参加过清华算协主办的系列活动参加过THUPC初赛参加过THUPC决赛参加过CodePlus参加过往期暑期培训ABCD提交参加过CodeLinkE以上都没参加过F投票(匿名)最多可选4项对于动态规划的了解情况基本不了解，全靠队友带只会做简单的动态规划题可以较熟练地过掉中档题多难的动态规划都一眼秒ABCD提交投票(匿名)最多可选1项动态规划

最长上升子序列问题LongestIncreasingSubsequence2147483647最长上升子序列问题LongestIncreasingSubsequence214748364721474836472147483647888

最长上升子序列问题LongestIncreasingSubsequence214748364721474836472147483647

最长上升子序列问题LongestIncreasingSubsequence21474836472147483647

动态规划（dynamicprogramming）可以用来解决组合优化问题尽管原指一类最优化方法，但在竞赛中，通常把类似于动态规划的递推计数等也称作动态规划动态规划的特点是阶段性，即生成解的过程可以分为多个阶段的决策阶段：由原问题经过恰当的划分得到的若干个相互联系的步骤状态：每个阶段开始面临的条件决策：给定某个阶段的状态，选择下一个阶段要进入何种状态策略：每个阶段的决策组成的序列动态规划

动态规划的适用场景

状态设计

从一维到多维

912348765从一维到多维897126354897126354

71711…1…8971…971…71…9797……

动态规划的设计

动态规划的转移

记忆化搜索Memoization递归求Fibonacci数列intfib(intn){ if(n<=2)return1; returnfib(n-1)+fib(n-2);}改为记忆化搜索intfib(intn){ if(vis[n])returnf[n]; vis[n]=true; returnf[n]=fib(n-1)+fib(n-2);}记忆化搜索Memoization不同类型的动态规划

序列DPdesirpiratese

NOIP2015子串作答peacepiecepacepeacepiecepeacepiece主观题10分

NOIP2015子串acepieceacepieceacepieceacepaceacaeeeppp

NOIP2015子串

背包问题

背包问题

0123456

01234560123456

背包问题

THUPC2021G赌徒问题作答主观题10分

THUPC2021G赌徒问题

THUPC2021G赌徒问题

正整数的线性组合

正整数的线性组合

区间DP

区间DP

恐狼后卫作答主观题10分

恐狼后卫34286910157

状态压缩DP

000

00

01

11

111Add#1Add#3Add#2Add#001001011

NOIP2016愤怒的小鸟作答主观题10分

NOIP2016愤怒的小鸟

最小斯坦纳树

最小斯坦纳树

最小斯坦纳树

最小斯坦纳树

最小斯坦纳树

最小斯坦纳树

ARC058E-IrohaandHaiku作答主观题10分

ARC058E-IrohaandHaiku

ARC058E-IrohaandHaiku

ARC058E-IrohaandHaiku

树型DP

树型背包

树型背包

树型背包

ARC083E-BichromeTree作答主观题10分

ARC083E-BichromeTree

ARC083E-BichromeTree

ARC083E-BichromeTree

ARC083E-BichromeTree

数位DP

数位DP

CF507D-TheMathsLecture作答主观题10分

CF507D-TheMathsLecture动态规划优化选讲

用单调栈/单调队列优化DP

NOI2005瑰丽华尔兹作答主观题10分

NOI2005瑰丽华尔兹

NOI2005瑰丽华尔兹

USCAO2008Mar-土地购买LandAcquisition作答主观题10分

USCAO2008Mar-土地购买LandAcquisition

USCAO2008Mar-土地购买LandAcquisitio