锐客网

  1. 首页 > it技术 > >

动态规划基础入门

动态规划

什么是动态规划呢？顾名思义，动态地进行规划？让我们先来看个小游戏：
引入：
大家在小的时候或许玩过跳房子的游戏，如果没玩过也没关系，我们对规则进行稍稍改动：

  • 龙龙在跳房子，每次可以选择跳1格或者k个格子，不允许往回跳，请问龙龙从第零格开始跳，跳到第n格一共有多少种方案？
注：跳格子的方案与顺序有关，比如先跳一格，再跳两格和先跳两格，再跳一格是不同种方案。
数据范围**：**2<=n<=60; 2<=k<=n
  • 如果你的数学够好，再加上数据范围是较小的，那当然可以用排列组合的思想来解决这道题，但仔细想想也还是挺复杂的，那么这时候就需要用到动态规划的思想了。
  • 我们假设在某一个时刻，龙龙正站在第i个格子，且这个i足够大（大到什么程度呢？只需要比k大就行了，至于原因，看下去就懂了），我们来思考，龙龙是怎么跳到第i个格子的呢？显然，龙龙一定是从第i-1或第i-k个格子跳过来的，那么我们就可以定义一个数组，就暂且称她为dp吧，dp[i]就表示跳到第i个格子一共有多少种方案。
  • 那么根据龙龙一定是从第i-1或第i-k个格子跳过来的，我们就可以列出这样一个方程： dp[i]=dp[i-1]+dp[i-k]
    这个方程非常重要，是解决这道问题的关键，在以后类似的动态规划题目中，我们把她称为状态转移方程。
  • 得到了状态转移方程，那么我们要求第
    dp[i]，也就是去求dp[i-1]和dp[i-k]，要求dp[i-1]和dp[i-k]，也就是去求dp[i-2]、dp[i-1-k]和dp[i-k-1]、dp[i-k-k]……，那么这样一直下去我们就需要知道一个边界条件，来完成我们的“递推思想”
    我们知道，当0
递推写法：
#include int main() { int n,k; //n表示跳到第n格有多少种方案，k表示每次可以跳一格或者k格 int dp[100]; //dp为状态转移数组 scanf("%d%d",&n,&k); for(int i=0; i

说完了递推写法，我们再来说说递归写法，递归的一个特点就是在过程中会调用自身，我们给上代码：
#include int n,k; //n表示跳到第n格有多少种方案，k表示每次可以跳一格或者k格 int search(int n) { if(n

看上去似乎也很简单，但其实隐藏了一个很大的“危机”，即使本题的数据范围较小，但还是很容易出现超时的情况，为什么小小的数据会产生超时呢？我们举个菲波那切数列的例子：
  • 所谓斐波那契，和我们的例子很相似，即dp[i]=dp[i-1]+dp[i-2],其中dp[1]=dp[2]=1，那如果运用了递归，那就在算dp[i]的时候，会调用自身，去求前两项，在求前两项时，又会调用自身，再往前求两项，但是这其实是重复计算没有必要的，因为前两项既然已经得到了，说明更之前的一定是已经算过了，那么我们可以用记忆化搜索的方式，给刚才的代码进行一小点处理，来保存之前已经求过的数据，避免大量的重复计算。
#include int n,k,dp[100]; //n表示跳到第n格有多少种方案，k表示每次可以跳一格或者k格 int search(int n) { if(dp[n]!=0) return dp[n]; if(n

定义
【动态规划基础入门】动态规划是一种通过拆分问题（发掘问题子结构），定义问题的状态（可理解为一单值函数）以及状态转移方程使问题能够通过递推（或递归等）的方式化为简单的问题（初值/边界条件）被解决的算法。
性质
  1. 需要满足无后效性，比如说本题的状态方程，一旦dp[i-1]和dp[i-k]为求dp[i]服务完后，就不能对后续的数据再产生影响了。
  2. 问题具有最优子结构性质，这样才能化为子问题进行解题。
难点
  1. 状态
    在复杂问题中，状态可能不是单变量定义，需要用到多维数组，如复杂的背包问题
  2. 状态转移方程
    状态转移方程不仅仅只有四则运算，可能会有积分号，求最大最小，等一系列奇奇怪怪的符号，不方便找
  3. 代码实现
    在oj上要考虑程序的运行速度，内存等问题，在用代码表示自己的思路时可能会出现“我的大脑明白了，但代码表达不了我的情感”的情况。

    推荐阅读


    上一篇：北大oj百练-1003

    下一篇：北大oj百练-2815:城堡问题