利用万网做网站,二手车网站制作,免费网页模板之家,google推广一年的费用想借着这一个题回顾一下动态规划问题的基本解法#xff0c;让解题方法清晰有条理#xff0c;希望更多的人可以更轻松的理解动态规划#xff01;
目录
【题目】
【本题解题思路】
【DP模版】
总体方针#xff1a;
具体解题时的套路#xff1a; 【题目】 【本题解题思…想借着这一个题回顾一下动态规划问题的基本解法让解题方法清晰有条理希望更多的人可以更轻松的理解动态规划
目录
【题目】
【本题解题思路】
【DP模版】
总体方针
具体解题时的套路 【题目】 【本题解题思路】
———类似题目覆盖墙壁 - 洛谷很多经典题解在里面
1、确定子状态
我最终要求解的是用两种类型的积木将2 x n的画卷填满时有着多少种组合方案。围绕最终要求解的问题确定子问题
所以子问题应该是在长度为n的情况下有多少种解法。
所以用一维数组dp[i] 存储长度为i 时的方案数。
2、确定转移的边界情况和初始状态
这里先正着推已知n3时dp[3]5那么就可以先明确n1,n2时对应的dp[i],即dp[1]1,dp[2]2;
然后发现没有什么明显的规律呢那就再倒着来
3、确定状态转移方式
为了方便表述设画卷长度为len
我想知道画卷长度为lenn时的值那么我就找他的上一层 lenn-1时的状态看看有没有什么关联。为了形成填满画卷的状态我的最后一块位置可以怎么摆放积木呢从积木的两种类型出发发现他可以形成四种状态。这里用分类的思想将所有的选择罗列出来找规律。
如图所示最后一次有如下选择 1最后一次选竖着的I 那么dp[n]dp[n-1]。
因为最后一位固定好了就这一种选择即1*dp[n-1]。如图1
2最后一次选横着的I ,那么为了填补上画卷第二行也只能选横着的I 这两个横着的I作为一个整体是一种填补画卷的方式。此时dp[n]dp[n-2];
如图2所示。
前两种状态都很明显但是如果选用L形的怎么罗列呢
3L型垂直翻转前后算两种状态如图3、4. 下面仅根据其中的一种情况来讨论最后因为翻转所有的结果×2 即可。
A.可以用两个L形成长度为3的整体来填补画卷dp[n]dp[n-3]如图5;
B.采用两个L和一个横着的I的方式形成一个整体作为一种方法填补dp[n]dp[n-4]如图6;
C.同上还可以采用在两侧两个L中间包裹多个横着的I的方式来填补每多一个横着的I相当于这个用于填补的图像整体的长度1。所以类推得到dp[n]dp[n-5]dp[n-6]... 如图7
综上所述形成填满画卷的前一个整体的状态可以采用如上这些方式所以他的方案总数就有:
dp[n]dp[n-1]dp[n-2]2*dp[n-3]dp[n-4]...dp[0];假如用前缀和sum[n]表示前n个长度的方案总和dp[n]sum[n-1]sum[n-3];
但是我这里只求了n1---3的情况n4时情况虽然有点复杂但是也还是不好求哈哈。
所以有没有什么化简的方式呢大家记不记得高考时第一个大题考的数组的性质这里就可以用来变换公式
dp[n]sum[n-1]sum[n-3];
dp[n-1]sum[n-2]sum[n-4];
上下相减发现 dp[n]-dp[n-1]dp[n-1]dp[n-3];
所以dp[n]2*dp[n-1]dp[n-3]
这就把递推公式推出来了完美撒花 【DP模版】
总体方针
凡是动态规划问题可以从以下三个角度考虑确定求解问题的基本思路
有时是二维问题或者多维问题时可以考虑用二维或者多维数组 动态规划问题具有两个性质
1无后效性每个子问题的解都是基于之前子问题的解而不受后续子问题解的影响。这意味着我们可以独立地解决每个子问题然后将这些解组合起来形成一个最优解。即当前状态的解只受此状态之前就是过去的状态的影响一经确定未来的状态不影响当前状态的结果。
换成人话就是当前状态的结果是由之前状态形成的一旦确定后续的状态对他没有影响
2子问题重叠性每个子问题之间类似于嵌套的关系我想求这个子问题就必须先解决比他规模更小的、具有同样规律的子问题。 具体解题时的套路
1、按照题目的求解问题确定子问题是什么把存储每个子问题的数据结构定义出来
2、根据题目中给的信息自己推理、枚举出来所有的可以获得的关于解的信息看看是否存在什么规律。这里推倒的方式往往是从边界开始往前推导观察前后状态之间的联系。或者是从初始状态向后推导找规律。
