动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题。

动态规划的适用范围

  • 如果要求一个问题的最优解(通常是最大值或者最小值),而且该问题能够分解成若干个子问题,并且小问题之间也存在重叠的子问题,则考虑采用动态规划
  • 无后效性:下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前状态是对以往决策的总结

动态规划的重点

  • 递归方程+边界条件

动态规划算法的两种设计

  • 自底向上(备忘录法):从大范围递推计算到小范围,不断保存中间结果,避免重复计算
  • 自顶向下(递推法):从小范围递推计算到大范围

经典问题分析

  • Leetcode爬楼梯问题

  • 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

  • 递推公式:DP[i]=DP[i-1]+DP[i-2]

  • 边界条件:DP[1]=1 DP[2]=2

  • 递推法

    1
    2
    3
    4
    5
    6
    7
    8
    class Solution {
    public:
    int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
    }
    };
  • 备忘录法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
    int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int results[n+1];
    results[1] = 1;
    results[2] = 2;
    for (int i=3; i<=n; ++i)
    results[i] = results[i-1] + results[i-2];
    return results[n] ;
    }
    };

算法分析

  • 不难看出备忘录法的时间复杂度是低于递推法的,其原因就在于递推法中计算了很多重复子问题,比如在此题中,当递归n-1和n-2的值时,n-1以下的部分就被计算了两次,浪费了时间,而在备忘录法中,保存了中间状态,就不用多次计算了。

分治法与动态规划

  • 按理来说分治法与动态规划的职能不同,分治法的子问题应当相互独立,而动态规划的子问题包含公共的子子问题,但有些问题两种方法都能解决。
    • 分治法将分解后的子问题看成相互独立的,通过用递归来做。
    • 动态规划将分解后的子问题理解为相互间有联系,有重叠部分,需要记忆,通常用迭代来做

最大子数组问题

  • 分治法:最大和子数组必定是左右两个子数组中的最大和子数组和跨越中间的最大和子数组中的一个

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution {
    public:
    int maxSubArray(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    int mid = nums.size()/2;
    vector<int> left(nums.begin(),nums.begin()+mid);
    vector<int> right(nums.begin()+mid,nums.end());
    int leftMax = maxSubArray(left);
    int rightMax = maxSubArray(right);
    int midMax = searchMidMax(nums,mid);
    return max(leftMax,max(rightMax,midMax));
    }

    int searchMidMax(vector<int>& nums,int mid) {
    if (nums.size() == 1) return nums[0];
    int maxl = nums[mid];
    int maxr = nums[mid];
    int sum = 0;
    for (int i = mid; i>=0; --i) {
    sum += nums[i];
    if (sum > maxl)
    maxl = sum;
    }
    sum = 0;
    for (int j = mid; j<nums.size(); ++j) {
    sum += nums[j];
    if (sum > maxr)
    maxr = sum;
    }
    return (maxr+maxl-nums[mid]);

    }
    };
  • 动态规划:遍历过程中保存最大值位置 MS[i] = max {MS[i-1], A[i]}.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    int FindMaxSubarray(int array[], int length)
    {
    int start = 0, end = 0; //记录最大子数组的起始位置(在数组中的下标)
    int MaxSumSub; //最大子数组的值
    int* dp = new int[length]; //动态规划记录

    dp[0] = array[0]; //初始为第一个数
    MaxSumSub = dp[0]; //最大值初始为第一个数
    int temp = 0; //

    for(int i = 1; i < length; i++)
    {
    if(dp[i - 1] <= 0) //前面的<0,直接丢弃
    {
    dp[i] = array[i];
    temp = i; //记录起始为止
    }
    else
    dp[i] = array[i] + dp[i - 1]; //往后求和

    if(dp[i] > MaxSumSub) //找到到i为止的最大子数组
    {
    MaxSumSub = dp[i]; //最大...
    start = temp; //标记起始
    end = i; //标记此时的结束位置
    }
    }

    return MaxSumSub;

    }
  • 从分治法的角度来看,数组被划分成了两部分,子问题相互独立

  • 从动态规划的角度来看,下一个子问题中包含了子子问题,也可以说是有重叠子问题

  • 以此可以看出从不同方向来分析同一问题,会有不同的结果

  • 另一方面,分治法的第二种拆分方法(分治法实践)从每次进行一次不对等分配的方向来看,确实符合分治法的思路,从每次递归找到一个更小的子问题的方向来看,又是动态规划。

  • 所以分治法和动态规划的界限也没有那么明显,或者说,分治法是一种方法,而动态规划是一种思路,两者本来就不矛盾。

感想

不得不说 虽然抽象后的动态规划进行求解的思路并不复杂,但具体的形式仿佛可以千变万化,和其他算法之间也有着千丝万缕的关系,不进行实践很难有进一步的认知,所以又到了刷Leetcode的时间了2333