数据结构与算法—动态规划学习之一

1. 什么是动态规划？

动态规划是求解“最优解”的一种数学方法。通常应用于一类具有如下特征的问题：

• 虽然是大问题，但是可以拆解为小问题
• 小问题同样存在更小的问题
• 有一些“原子”问题，即那些不可再分的问题，通常是动态规划中的“边界条件”

当你看到一些满足以上要求的题目之后，那么你可以考虑使用动态规划的方法去解这道题。算法题与数学题的区别之一，就是一个公式、解题思路并不一定可以解决所有该类型的题目，更需要做出：
“适当的调整”。
这是除了动态规划外，另一个应该想到的重点。

2. 如何求解动态规划

根据该博客的描述，可以采用“五个步骤”尝试解题。

• 分析题目，题目是否要求解“最优解”
• 自顶向下的分析，问题是否可以拆解，子问题是否可以继续拆解…
• 自下向上的分析，总结递推的规律，找出状态转移方程。
• 边界问题，下边界、上边界的界定。
• 通常用dp[Input+1]数组，存储递推结果。其中Input为输入规模。
  我的数学功底较差，上面的描述仅仅根据个人理解，详细的可以参考开头的链接。

3. 例举问题

不如从几个简单的动态规划题目来逐步理解这些抽象的概念吧！

问题1:

青蛙跳台阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法。

• 1.根据题意，判断是否有求最优解的意味
  遇到问题了，但从题目是看不出来有“最优解”的感觉，那么是否和动态规划无关呢？继续往下看。
• 2.自上向下分析问题，找到大问题的子问题
  例如，跳6级台阶，最后一跳，要么是从4级一下跳到6级（高度：2）
  要么是从5级一下跳到6级（高度：1），所以问题可以看作是：

 青蛙跳到了6级，请问有多少种跳法 = 青蛙跳到了5级，请问有多少种跳法？ + 青蛙跳到了4级，请问有多少种跳法？ 

讯享网Jump(6) = Jump(5) + Jump(4) 所以问题可以化作：Jump(n) = Jump(n-1) + Jump(n-2) 

• 3.自下向上分析问题，找到问题之间的关联
  那么由问题可以简单的归纳出：
  Jump(0) ->无意义
  Jump(1) = 1 一次跳一级
  Jump(2) = 2 一次跳一级 + 一次跳两级
  根据2可知：
  Jump(3) = Jump(1) + Jump(2)
  则：Jump(3) = 1 + 2 = 3;
  那么问题就可以进行迭代了，我们可以从边界迭代到我们想要的答案。

public class DynamicProgramming { 
    public static int Jump(int N){ 
    //动态规划的数组大小，因为0不用，所以要到N+1大小 int dp[] = new int[N+1]; //初始化边界 dp[0] = -1; //无意义的跳跃 dp[1] = 1; //1级台阶只用跳1次 dp[2] = 2; //2级台阶可以 1+1 也可 2 一步跳上去 //根据分析，N=3的时候就可以迭代了 if(N >= 3){ 
    for (int i = 3; i <= N; i++) { 
    dp[i] = dp[i-1] + dp[i-2]; } } //返回对应的目标 return dp[N]; } public static void main(String[] args) { 
    System.out.println("青蛙要跳 6 级，所以一共有："); System.out.println(Jump(6) + "种跳法"); } } 

问题2:

给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>=1并且m>1),每段绳子的长度记为k[0],k[1],…,k[m],请问k[0]k[1]…*k[m]可能的最大乘积是多少？

例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18.

• 1.分析题目，是否有最优解的感觉？
  有的，求出剪m次的情况下，最大的乘积
• 2.自顶向下分析问题
  例如长度为n = 8，m = 2可以剪为{1,7},{2,6},{3,5},{4,4}
  只要直到 Max{[f(1) * f(7)],[f(2) * f(6)],[f(3) * f(5)],[f(4) * f(4)]}就可
  因为f(1)已知， f(1) = 1;
  f(7)可以继续分为{1,6},{2,5},{3,4}
• 3.自下向上分析问题
  f(1) = 1 不能剪，f(1) = 1;
  f(2) = 2 剪一次，{1,1} f(1) * f(1) = 1; 比自身小
  那么"没必要"为求乘积大小而减掉它
  f(3) = 3,m=1时 {1,2} f(1) * f(2) = 1 * 2 = 2;
  m=2时 {1,1,1} f(1)*f(1)*f(1) = 1;都比自身小
  “没必要”
  f(4) = 4, 最合适剪一次，{2,2} f(2) * f(2) = 4 {2,2}是在{ {1,3},{2,3}}中找到
  f(5) = 6, 最合适剪一次，{2,3} f(2) * f(3) = 6 {2,3}是在{ {1,4},{2,3}}中找到
  …
  注意，以上都是不同长度下，经过剪刀函数f的作用下，得到的最优解
  看似，f(8)要拆分为{1,7},{2,6},{3,5},{4,4},只剪了一次，其实实质上应该这样理解：
  首先，这种拆分得到的组，最大不会超过8，也就是1-7，经过上面的迭代，我们已经得到了所有1-7的最优的解即:
  f(1) - f(7)
  从中找Max{[f(1) * f(7)],[f(2) * f(6)],[f(3) * f(5)],[f(4) * f(4)]}，
  意思是找一组最优的分组策略，例如f(3)*f(5)就是最优的，代表的是 3 * 2 * 3,f(3)没必要剪，f(5)代表之前求出的最优：2 * 3.
  和题目完全吻合。

讯享网public class DynamicProgramming2 { 
    public static int cutting(int m){ 
    //无意义的长度 if(m < 0) return -1; //0不用 int dp[] = new int[m+1]; //存储迭代最大值 int max = 0; dp[0] = -1; //无意义的长度 dp[1] = 1; //f(1) = 1 不能剪，f(1) = 1; dp[2] = 2; //f(2) = 2 没必要剪 dp[3] = 3; //f(3) = 3 没必要剪 //从4开始迭代 //迭代公式：f(n) = max{f(1)*f(n-1),f(2)*f(n-2)...,f(n/2)*f(n-n/2)} for (int i = 4; i <= m; i++) { 
    for (int j = 1; j <= m/2; j++) { 
    int val = dp[j] * dp[i-j]; max = max > val ? max : val; //最优解要求我们求解最大值，所以这里要求出最大值迭代 } dp[i] = max; //记录已经求出的结果 } return dp[m]; } public static void main(String[] args) { 
    System.out.println(cutting(8)); } } 

问题3:

你将会获得一系列视频片段，这些片段来自于一项持续时长
为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。
我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7]
可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，
并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。
返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

示例 1：

• 输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
• 输出：3
• 解释：
  我们选中 [0,2], [8,10], [1,9] 这三个片段。
  现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。

示例 2：

• 输入：clips = [[0,1],[1,2]], T = 5
• 输出：-1
• 解释：
  我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。

示例 3：

• 输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
• 输出：3
• 解释：
  我们选取片段 [0,4], [4,7] 和 [6,9] .

示例 4：

讯享网

• 输入：clips = [[0,4],[2,8]], T = 5
• 输出：2
• 解释：[0,4],[2,8]覆盖了整个片段

注意：你有可能录制超过比赛长度的视频。

• 分析题目

  本题确实存在最优解的思想。

• 自顶向下分析问题

  我们从具体的角度来思考这个问题，首先如果输入T = 10，那么我们就需要[0,10]这个区间被全部覆盖。另外一点很重要，本题目的所有输入，决定了题目的输出，也就是不同用于那些通过边界条件递推到目标的问题，它们有着固定的答案，但是这道题的答案取决于我们的输入，我们需要从输入中去寻找最优的解。所以我们假设输入和示例一 一样：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]。
  很简单的就可以想到的是，如果要覆盖整个视频长度，我们需要从0开始，超过10结束。[0,2]与[8,10]就是必选的片段。
  题目隐含了一个条件是：输入T总是位于一个区间(ai,bj],这样一个左开右闭区间。本题的10就位于区间[8,10]，所以ai = 8，bj = 10，那么当我们选择了这个片段，就证明要求的[0,10]已经被覆盖了后半部分，也就是[8,10]这部分。那么现在的问题是不是变成了：[0,8]的最优覆盖问题？也就是从求解F(10)变成了求解F(8)。也就是求解F(ai)显然，问题是可以拆分的。
  继续分析，由上面的叙述可以知道，现在T = 8，根据我们的输入，8位于区间(1,9],也位于区间(5,9],此时面临选择，那么依据是什么呢？
  到这一步，你会发现选择的过程没完没了，因为我们在这里比较了F(1)与F(5)之后，又有可能要继续细分问题往下比…还记得动态规划的思想吗？可以从边界迭代到目标，所以当我们输入了10，我们应该让程序帮我们迭代算出F(1) - F(9)，然后再计算F(10)的时候，就可以利用之前的值了。
  透过上面的分析我们可以总结出状态转移方程：
  
  +1的意思是，当该区间满足要求，那么就要在F(ai)的基础上，算上这个区间。

• 自下向上的分析
  clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]
  T = 0，无意义，所以F(0) = 0;
  T = 1，它位于区间[0,2]，所以F(1) = min{F(0) + 1} = 1
  T = 2，它位于区间[0,2],[1,9],[1,5]，所以F(2) = min{F(0) + 1,F(1)+1,F(1)+1} = 1
  T = 3, …

public class LeetCode31 { 
    public int videoStitching(int[][] clips, int T) { 
    //无意义的输入 if(T < 0) return -1; //动态规划 int[] dp = new int[T + 1]; //首先给所有的dp赋予一个极大值，这是用于迭代到最小值的初始化 Arrays.fill(dp,Integer.MAX_VALUE - 1); dp[0] = 0; //输入0，缺省为0 //从1开始迭代 for (int i = 1; i < dp.length; i++) { 
    //遍历二维数组，也就是输入的视频片段 for(int[] clip : clips){ 
    //如果所给的输入T位于(ai,bi]之间,那么dp[T] = min(dp[ai]) + 1 if(i > clip[0] && i <= clip[1]){ 
    dp[i] = Math.min(dp[i],((dp[clip[0]])+1)); } } } return dp[T] == (Integer.MAX_VALUE - 1) ? -1 : dp[T]; } } 

问题4:

• 分析题目

首先这道题提供了一个递归函数，通过简单的语法就可以实现。但是对于W(15,15,15)这样的输入，递归的次数将十分的吓人。经过测试，我们发现一个比较小的输入W(5,5,5)都有近1500次的递归调用。那么这道题与动态规划的关系是什么呢？根据前面几道题的洗礼，我们知道了动态规划一般和递推脱不了干系，那么递归一定程度上，是可以转化为递归的。那么，对于某些输入，递归调用次数过多的原因在什么地方呢？答案是：重复计算。所以我们需要记忆化搜索，也就是把重复的答案记下来，下一次直接用。这就十分类似动态规划了。

• 自顶向下分析问题

• 自下向上分析问题

边界条件的确定已经略做了分析。考虑一些超出范围的处理方式就可以。

• 注意

这一题给了我们一个新的思路，对于某些非常难遍历的多维数组，似乎可以采用递归函数的方式来初始化。

讯享网public class LeetCode32 { 
    public static int dpW[][][] = new int[21][21][21]; public static int w(int a,int b,int c){ 
    if(a <= 0 || b <= 0 || c <= 0){ 
    return 1; }else if (a > 20 || b > 20 || c > 20){ 
    return dpW[20][20][20] = w(20,20,20); } else if (dpW[a][b][c] != 0){ 
    return dpW[a][b][c]; } else if (a < b & b < c){ 
    dpW[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c); }else{ 
    dpW[a][b][c] = w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1); } return dpW[a][b][c]; } public static void main(String[] args) { 
    System.out.println(w(1,1,1)); } }