非原创(懒得自己写了
动态规划思想
一、动态规划概念:
-
动态规划(dp)是研究多步决策过程最优化问题的一种数学方法。在动态规划中,为了寻找一个问题的最优解(即最优决策过程),将整个问题划分成若干个相应的阶段,并在每个阶段都根据先前所作出的决策作出当前阶段最优决策,进而得出整个问题的最优解。即记住已知问题的答案,在已知的答案的基础上解决未知的问题。
-
在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。可以自行创建一个动态规划表dp,dp一般是个数组,可以是一维也可以是二维数组,根据题中的需要,然后将子问题的最优解填入其中,方便在求解之后的子问题时可以方便调用,进而求出整个问题的最优解。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。
-
动态规划有两种实现方法,一种是递推,另一种是记忆化搜索。两种方法时间复杂度完全相同,但是,递推的效率要比记忆化搜索高不少,而且以后的大量优化技巧都建立在递推上(滚动数组、单调队列、斜率优化……)。所以,我们一般用递推来写动态规划。
二、动态规划的性质:
(1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
(2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
(3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
三、动规解题的一般思路:
动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
(1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
(2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。 一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。
四、解题步骤:
-
拆分问题;
-
定义状态并找出初状态;
-
状态转移方程。
五、算法实现的步骤:
1、创建一个一维数组或者二维数组,保存每一个子问题的结果,具体创建一维数组还是二维数组看题目而定,基本上如果题目中给出的是一个一维数组进行操作,就可以只创建一个一维数组,如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值,比如背包问题中的不同物体的体积与总体积,找零钱问题中的不同面值零钱与总钱数,这样就需要创建一个二维数组。注:需要创建二维数组的解法,都可以创建一个一维数组运用滚动数组的方式来解决,即一位数组中的值不停的变化,后面会详细徐叙述
2、找到初始条件,设置数组边界值,一维数组就是设置第一个数字,二维数组就是设置第一行跟第一列的值,特别的滚动一维数组是要设置整个数组的值,然后根据后面不同的数据加进来变幻成不同的值。
3、根据初始条件或边界条件,找出状态转换方程,也就是说找到每个状态跟他上一个状态的关系,根据状态转化方程写出代码。
4、返回需要的值,一般是数组的最后一个或者二维数组的最右下角。
六、例题
应用举例1:
题目描述:超级台阶
有一楼梯共m级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第m级,共有多少走法?
注:规定从一级到一级有0种走法。
输入格式
输入数据首先包含一个整数n(1<=n<=100),表示测试实例的个数,然后是n行数据,每行包含一个整数m,(1<=m<=40), 表示楼梯的级数。
输出格式
对于每个测试实例,请输出不同走法的数量。
输入输出样例
输入
2
2
3
输出
1
2
代码思路:
首先考虑题中要求的是走上m级台阶总共有多少走法,不妨设dp(m) = ans;
再考虑下子问题:
dp(m-1) 就是走上m-1级台阶总共有多少走法
dp(m-2)就是走上m-2级台阶总共有多少走法
子问题与原问题的关系:题中告诉我们每次只可以跨一级或两级,那么反过来理解就是,第m级台阶可能是m-1或者m-2级台阶走上来的,如果已经求出了dp(m-1)和dp(m-2),很明显:
dp(m) = dp(m-1)+dp(m-2);
代码实现:
#include <iostream>
using namespace std;
int n;
int m,dp[3];//创建dp数组,之用来存储三级台阶
int main(){
cin>>n;
for (int i = 1; i <=n ; ++i) {
cin>>m;
dp[0] = dp[1] = 1; // 初始化第一、二级台阶为1,这样之后的可以递推
if(m<2){
break;
}
for(int j=2;j<m;j++){ //从第二级开始递推
dp[j%3] = dp[(j-1)%3]+dp[(j-2)%3];//这里使用滚动数组来优化空间
}
cout<<dp[(m-1)%3]<<endl;
}
return 0;
}
题目很多,洛谷就有很多毒瘤dp
洛谷动态规划例题
写的真好%%%
%%%%%%%