资源描述：
《动态规划从入门到精通(Ⅰ).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1动态规划入门到精通(Ⅰ)一些前话——xiper做了专题，感觉自己很强，然后比赛还是什么DP都做不来（有很多时候压根就没看出来是DP），正常吗？正常，一般来讲新人（没有基础的）刚开始时没有建立起DP思维，即便做了专题，短时间内肯定还是云里雾里的，导致比赛的时候写不出DP，同时DP本身就难，大爷们都不一定次次能出DP，更不要说新人了怎么快速入门，能又快又准的写出基础的DP（套路DP题）掌握基本的写法，理解经典模型的转移搞个数字三角形从上往下走，每次可以向左下或右下走一个，直到最下行，问经过数字的和最大
2、是多少？13111112736614158127132411朴素贪心13+？左？右？不说更多，显然在第二行已经迷失方向13111112736614158127132411如何求解如果利用转移方程求解原问题？f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j]1、从上向下转移，即i从小到大？2、从下向上转移，即i从大到小？观察转移方程的性质因为第i行的解要由第i-1行的解得到，所以必须从上向下转移如何求解边界条件，特殊处理即可。j=1:f[i][j]=a[i][j]+f
3、[i-1][j]j=i:f[i][j]=a[i][j]+f[i-1][j-1]代码展示for(inti=2;i<=n;i++)//初始化边界f[i][1]=a[i][1]+f[i][1];for(inti=2;i<=n;i++)//初始化边界f[i][i]=a[i][i]+f[i][i-1];for(inti=3;i<=n;i++)for(intj=1;j<=m;j++)f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j]更多选择？有了转移方程f[i][j]=max(f[
4、i-1][j],f[i-1][j-1])+a[i][j]容易得dfs(i,j)=max(dfs(i-1,j),dfs(i-1,j))时间？可以使用数组f[i][j]=dfs(i,j)记忆化搜索代码展示memset(f,-1,sizeoff)intdfs(inti,intj)if(f[i][j])returnf[i][j]=max(dfs(i-1,j-1),dfs(i-1,j));returnf[i][j];为何还要记忆化搜索？滑雪为了获得速度，滑雪的路径必须向下倾斜，每次可以向上下左右4个方向滑行。
5、区域由一个二维数组给出，每个数字代表该点的高度。求滑行的最长距离。12345 161718196 152425207 142322218 131211109困难？能用递推的方法做么？哪里不能？没有明确的依赖顺序，无法直接用递推进行转移解决办法记忆化搜索滑雪的记忆化搜索实现概念动态规划是一种用于求解包含重叠子问题的最优化问题的思想。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。要点状态定义：如何描述一个子问题？定义要明确。状态转移方程：如何由子问题构造出原问题的
6、解？边界条件、初始条件递推顺序总结算法设计状态定义状态转移（递推顺序很重要）边界条件、初始条件条件无后效性最优子结构再搞个数字三角形从上往下走，每次可以向左下或右下走一个，直到最下行，问经过数字的和与20的差绝对值最少是多少？13111112736614158127132411总结如何利用转移方程求解递推递归求解通项公式如何看待记忆化避免大量重复计算简洁明了，方便理解递推比较繁琐，或没有明确的依赖顺序（图）18典型模型温馨提示代码展示中代码仅做演示用，请勿不经思考照搬，WA者自负01背包在n件物品取
7、出若干件放在空间为V的背包里，每件物品的体积为w1，w2……wn，与之相对应的价值为p1,p2……pn。01背包定义状态dp[i][j]：考虑前i件物品，选的物品总体积=j的情况下价值和的最大值转移方程：O(n*V)dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+pi)代码展示01背包定义状态dp[i][j]：考虑前i件物品，选的物品总体积<=j的情况下价值和的最大值转移方程：O(n*V)dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+pi)转
8、移方程一样，边界条件不同代码展示01背包定义状态dp[j]：选的物品总体积<=j的情况下价值和的最大值转移方程：O(n*V)dp[j]=max(dp[j],dp[j-wi]+pi)代码展示状态压缩状态压缩是状态维度较多，同时每个维度状态较少的一类问题，例旅行商问题(tsp)。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，要求最短长度。状态压缩状态dp[i][j]为访问了城市集合i最后在城市j的最短长度。i为sum(ak<<
