“动态规划”，虽然听起来就比较高大上，但了解到原理后，就会发现它实际上并没有想象的那么难。Dynamic Programming中的Programming，并不是表示编程，而是指递推。一步步向下，根据当前的状态推进后面的状态。

如果一个问题能够用递归来解决，那辅助使用记忆化的手段，我们就能通过一个递推公式来描述问题的“通解”，利用这个“通解”来解决问题，就叫动态规划

状态的定义

动态规划问题中，通常使用类似于opt[n], dp[n], fib[n]等形式的数组来表达

状态转移方程

也叫“DP方程”、递推方程，形如opt[n] = best_of(opt[n-1], opt[n-2], …)，描述的是不同状态间的递推关系。

最优子结构

最优子结构描述了这样一种性质：问题的最优解可由其子问题的最优解得出，即问题的最优解包含子问题的最优解

例一：从Fibnacci数列说起

以经典的斐波那契数列问题为例，再来深入理解一下动态规划思想的由来：

斐波那契数列是这样一串数字：0, 1, 1, 2, 3, 5, 8, 13, 21, …

归纳一下不难得到，该数列的递推公式可表示为： F[n] = F[n-1] + F[n-2]

怎么求第n项呢？根据递推公式，我们知道Fib(n)=Fib(n-1)+Fib(n-2)。当n比较大时我们还要将Fib(n-1)继续往下推，当n=0、1时才能直接返回0、1，由于每一项的递推公式都是一样的，因此可以得出初步的一个思路就是递归，将递推公式封装进入函数中，不断调用最后得出结果

递推法求Fib(n)

但是这样的递归调用存在两个较大的问题：

  1. 优化时间复杂度极高，根据算法的调用树可以看到，树深为n，一个结点n有两个子节点（n-1和n-2），因此总的时间复杂度量级为O(2n)，这意味着算量是指数级增长的。2. 存在大量的重复计算，比如计算Fib(6)的过程中，需独立调用计算Fib(0)5次、Fib(1)6次、Fib(2)5次……这样的重复计算，必然是对资源的极大浪费

在这样的背景下，就有必要对朴素的递归方法进行优化，才能将其时间复杂度降低至合理的范围，减少甚至避免重复计算。

首先是避免重复计算，采用记忆优化的方法。维护一个全局的Fibnacci数列数组，每次调用Fib(n)之前先到数组里面找，没有的话再计算，最后把结果更新到数组中。这样，就减少了重复计算的问题，算法复杂度也大幅度下降

然后，我们将数列第n项求解的方向，从倒推变为正推，从递归调用变成正向循环推导，则这样就不需要原来的辅助数组，空间复杂度降为了O(1)。

正推Fib(n)

将递归和记忆优化的方法结合起来，使用递推公式进行计算，时间复杂度降到了O(N)，空间复杂度降到了O(1)。

例二：有障碍条件路径数目

在一个如下图所示的棋盘中存在若干障碍，起点和终点分别位于左上角和右下角，问从起点到终点有多少条路径

有障碍路径数目

长N，宽M的棋盘，若无障碍，总路径数应为排列组合CM+NM的结果

首先对题目进行初步分析，尝试使用递归进行解决。小人在图中移动的方向可以是上、下、左、右（这里稍有缺陷，假设限制只能向右和向下移动）。从起点到终点，每一步的下一步有两种可能：向下或向右，若当前位置下边或右边有障碍则不计路径，否则路径数+1。依次向下递推，不断调用，直到到达终点：

int countPaths(boolean[][] grid, int row, int col) {
    if (!validSquare(grid, row, col) return 0;//碰到边界或障碍不计
    if (isAtEnd(grid, row, col) return 1;//到达了终点
    return countPaths(grid, row+1, col) + countPaths(grid, row, col+1);//右边和下边的路径数之和
}

这样的方法和前面例一一样，存在大量的重复计算，时间复杂度也达到了O(2n)甚至更高。因此改进的思路，第一点还是记忆优化，然后转换方向变为从终点到起点递推

//状态转移方程：
opt [i, j] = opt[i+1,j]+opt[i,j+1]
——————————————————————————————————
opt[M][N-1]=opt[M-1][N]=opt[M][N]=1

for(i=M;i>0;i--):
    for(j=N;i>0;j--):#从终点向起点递推
        if a[i,j] ='空地':#具体可用isvalidSquare(grid,row,col)实现
            opt[i,j]=opt[i+1,j]+opt[i,j+1]
        else: #石头或边界
            opt [i,j]=0

return opt[0][0]

时间复杂度上，由于只需要一个二重循环，O(M·N)

小结

  1. 动态规划，实际是递推的过程，只能规划到下面紧邻的步，一开始先实现递归，利用记忆化进行加速，最后转化为递推
  2. 状态定义的方式，一般是一个状态数组
  3. 状态转移方程，一般存在很多if-else分支
  4. 最优子结构，问题本身的最优解由子问题的最优解构成

DP vs 回溯 vs 贪心

  • 回溯（递归），存在许多重复计算
  • 贪心，永远只求局部最优
  • DP，就像前两者的“集大成者”，记录局部最优子结构/多种记录值

实战题目

  1. 爬楼梯

    • 思路一：回溯思想，递归实现。假设到终点的走法数是f(n)，到倒数第一级为f(n-1)，倒数第二级为f(n-2)，显然有f(n)=f(n-1)+f(n-2)（要么一步到终点，要么两步到终点），用递归实现+记忆优化
    • 根据上面的分析，直接用正向递推实现，时间复杂度O(N)，同时把状态定义从数组转为三个变量，空间复杂度O(1)
      • 数组版：
        public int climbStairs(int n) {
if(n <= 2) return n;
int[] mem = new int[n];
mem[0] = 1;
mem[1] = 2;
for(int i = 2; i<n; i++){
 mem[i] = mem[i-1] + mem[i-2];
}
return mem[n-1l;
}
      • 变量版：
        public int climbStairs(int n){
if(n <= 2) return n;
int one_step_before = 2;
int two_steps_before = 1;
int all_ways = 0;
for(int i = 2; i <n; i++){
 all_ways = one_step_before + two_steps_before;
 two_steps_before = one_step_before;
 one_step_before = all_ways;
}
return all_ways;
}
      • Python：
        def ClimbingStairs(self, n):
x, y = 1 , 1
for _ in range(1, n):
 x, y = y, x + y#一行多变量同时赋值，后面的赋值不会因前面先进行赋值而受到影响
return y

  2. 三角形最小路径和
    给定一个三角形形式的二维数组，问从顶点到最底层某点的路径上数字之和最小是多少（向下一层走的时候，只能到下边紧邻两个数字）

    • 思路一：递归求解，顶点层调第二层左右，第二层左调第三层左右，第三层调第四层左右……一直调到最底层，每层调的时候当前节点数字累加到全局变量存储到一个数组，最后数组排序即可
    • 简单的贪心算法，不一定能得到全局最优解，下一层最小的数字不能保证再下一层最小的数字
    • 动态规划，递推。两个要点：状态定义和DP方程。转变递推方向，从顶推底变为从底推顶，记DP[i,j]为从底到点Triangle[i,j]所经历路径的最小值，则DP[i,j]=min(DP[i+1,j],DP[i+1,j+1])+Triangle[i,j] “相当于开了上帝视角”，把后面的情况“提前看到了”
      • c++版：
        class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle)
{
 vector<int> mini = triangle[triangle.size( )-1];
 for ( int i = triangle.size() - 2; i>= 0 ; --i )
     for ( int j = 0; j < triangle[i].size() ; ++j )
         mini[j] = triangle[i][j] + min(mini[jl,mini[j+1]);//mini可以复用，直接把值记录在mini[j]即可，不再用二维数组
 return mini[0];
}
}
      • python:
        def minimumTotal(self, triangle):
if not triangle: return 0
res = triangle[-1]#-1表示最后一行
for i in xrange(len(triangle) - 2，-1，-1):
 for j in xrange( len(triangle[i])):
     res[j] = min( res[jl, res[j+1]) + triangle[i][j]
return res[0]

  3. 乘积最大子序列

    • 思路一：暴力搜索

    • 思路二：动态规划，从最后向前推。以DP[i]表示从a[0]到a[i]点，可能的最大乘积，则分为两种情况：

      • 若a[i]>0，则DP[i-1]*a[i]即能表达DP[i]
      • 若a[i]<0，则简单的dp[i-1]*a[i]是一个负值，并不能表达dp[i] 因此，一个变量不够了，需要用两个变量，一个存最大值，一个存最小值，即：
      • 若a[i]>=0，则DP[i,0]=DP[i-1,0]*a[i]
      • 若a[i] <0，则DP[i,0]=DP[i-1,1]*a[i]

    • 二维滚动数组版：

      def maxProduct(self, nums):
if nums is None: return 0
dp = [[0 for _ in range(2)] for _ in range(2)]

dp[0][1], dp[0][0], res = nums[0], nums[0], nums[0]

for i in range(1,len(nums)):
   x,y = i % 2，(i - 1)%2
   dp[x][0] = max(dply][0] * nums[i],dp[y][1] * nums[i], nums[i]
   dp[x][1] = min(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i]
   res = max( res,dp[x][0])
return res
    • 双变量+暴力美学版（不利于扩展）：
      def maxProduct(self, nums):
if nums is None: return 0
   res, curMax, curMin = nums[0], nums[0], nums[0]
for i in range(1,len(nums)):
   num = nums [i]
   curMax,curMin = curMax * num,curMin* num
   curMin,curMax = min(curMax,curMin，num), max( curMax,curMin,num
   #print( curMin, curMax)
   res = curMax if curMax > res else res
return res

  4. 股票买卖系列
    题目描述：输入参数是一串数字，表示每天的股票价格。根据不同的价格和交易限制，确定最优的交易策略，返回潜在的最大收益，不同题目都有共同限制：任何时刻持有股票不得超过1股

    • 股票买卖时机
      只能买一次
      • 思路一：不考虑动态规划，简单遍历一次，记录最小值和最大值，返回最大值减最小值
        def maxProfit(self, prices):
if not prices: return 0
res = 0
profit = [[0 for i in xrange(3)] for i in xrange(len(prices))]
profit[0][0], profit[0][1],profit[0][2] = 0, -prices[0], 0
for i in range(1,len(prices)):
profit[i][0] = profit[i-1][0]
profit[i][1] = max(profit[i-1][1], profit[i-1][0] - prices[i])
profit[i] [2] = profit[i-1][1] + prices[i]
res = max( res,profit[i][0], profit[i][1],profit[i][2])
return res
      • 思路二：第四题的具化

    • 股票买卖时机-2
      可以买入卖出无数次

      • 思路一：同样简单遍历，遍历到后一天价格高于前一天价格的时候，在前一天买入，持有到价格开始下降的时候卖出，继续遍历重复上述行为。

        class Solution(object):
def maxProfit(self, prices):
if not prices: return 0
profit = [[[0 for _ in xrange(2)] for _ in range(3)] for _ in xrange(len(prices))]
profit[0][0][0], profit[0][0][1]=0,-prices[0]
profit[0][1][0], profit[0][1][1]=-maxint,-maxintprofit[O][2][0], profit[0][2][1] =-maxint,-maxint

for i in range(1,len(prices)):
    profit[i][0][0] = profit[i-1][0][0]
    profit[i][0][1] = max(profit[i-1][0][1],profit[i-1][0][0] - prices[i])
    profit[i][1][0] = max(profit[i-1][1][0],profit[i-1][0][1] + prices[i])
    profit[i][1][1] = max(profit[i-1][1][1],profit[i-1][1][0] - prices[i])
    profit[i][2][0] = max(profit[i-1][2][0],profit[i-1][1][1] + prices[i])
end = len(prices)-1
return max(profit[end][0][0],profit[end][1][0],profit[end][2][0])
      • 思路二：第四题的具化
    • 股票买卖时机-3
      只能买卖两次，前一笔卖出后一笔才能买入第二笔
      • 思路一：暴力求解，
        public int maxProfit(int[] prices){
int hold1 = Integer.HIN_VALUE,hold2 = Integer.MIN_VALUE;
int release1 =0, release2 =0;
for(int i:prices){
// Assume we only have a money at first
release2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far
hold2= Hath.max(hold2, release1-i); // The maximum if we've just buy 2nd stock so far
release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far
hold1=Math.max(hold1, -i);// The maximum if we've just buy ist stock so far.
}
return release2;//Since release1 is initiated as 0, so release2 will always higher than release1.
}
      • 思路二：第四题的具体化
    • 股票买卖时机-4
      只能买k次
      • 是前面三题的泛化情况，适合用DP求解。
      • 首先定义状态和状态方程。此处问题求解的事最大股票收益，初步考虑用一个数组max_profit[]存储，第i项就表示到第i天能获得的最大收益。
      • 检查上述状态定义，发现其并不能满足一些约束条件：比如当前没有持有股票，就不能卖出。因此增加一个维度表示是否持有。则：MP[i][0]=max(MP[i-1][0]（前一天没有，今天按兵不动）,MP[i-1][1]+a[i]（前一天有的，今天卖了）) ,MP[i][1]=max(MP[i-1][1],MP[i-1][0]-a[i]（前一天没有，今天买入）)
      • 二维的状态仍不能判断之前已经交易过多少次，继续进行改造，增加一个维度，第三维长度k，记录前面交易次数。调换一下顺序变为MP[i][k][j]，i∈[0,n]，k∈[0,K]，j∈[0,1]
      • 在上一步的前提下，递推公式变为：MP[i][k][0]=max(MP[i-1][k-1][1]+a[i],MP[i-1][k][0])，MP[i][k][1]=max(MP[i-1][k-1][0]-a[i],MP[i-1][k][1])
    • 含冻结期的股票买卖时机
      • 卖完第二天才能买入
    • 带交易费的股票买卖时机
      • 收取一定交易手续费

  5. 最长上升子序列
    输入元素是一个数字数组，返回最大的上升子序列长度。不一定连续，只要求选取的元素大小是上升的即可，返回子序列元素个数

    • 思路一：直接暴力递归，递归实现时间复杂度O(2n)
    • 思路二，DP。状态定义：DP[i]表示第i个元素作为上升序列尾时上升序列最大长度。则DP[i]=DP[i-1]+1（a[i-1] \<= a[i]）或DP[i-1]（a[i-1] > a[i]），统一总结为DP[i]=max{DP[1],DP[2],……D,P[i-1]}+1.算法时间复杂度O(N2)
      public int length0fLIS(int[] nums){
if (nums ==null || nums.length == 0){
   return 0;
}
int res = 1;
int[] dp = new int[nums.length + 1];
for (int i = 0; i < nums.length; ++i) dp[i] = 1;
   for (int i = 1; i < nums.length; ++i){
       for (int j = 0; j < i; ++j) {
           if (nums[j] < nums[i]){
               dp[i] = Math.max(dp[i], dp[j] +1);
           }
       }
       res=Math.max( res, dp[i]);
   }
return res;
}
    • 思路三，辅助二分查找进行数组元素调整。具体思路：维护一个数组LIS，遍历一次原始数组nums，若nums[i] > LIS[end]，则LIS[end++]=nums[i]，若LIS[begin] < nums[i] < LIS[end]，则查找LIS中大于nums[i]且最小的元素，用nums[i]替换之。否则，若nums[i] < LIS[begin]，清空再插入。时间复杂度O(N*logN)（每个元素遍历+二分查找）
      int lengthOfLIS(vector<int>& nums){
int n = nums.size();
if (n <= 1) return n;
vector<int> res;
res.push_back(nums[0]);
for (int i = 1; i < n; ++i){
   if (dp.back() < nums[i]){
       dp.push_back(nums[i]);
   } else {
       auto itr = lower_bound(dp.begin(), dp.end(), nums[i]);
       *itr = nums[i];
   }
}
return dp.size();

  6. 零钱兑换
    输入参数：钱币面额，总金额，返回值：最小的钱币数，若无解返回-1。

    • 思路一：类似于走台阶问题，每次走1，2，5步，最高11阶。暴力求解，1步最多11次，2步最多5次，5步最多2次，三者之和最小,时间复杂度O(N2)
    • 思路二：贪心法，每次优先跨大步。不能保证全局最优解，放弃
    • 思路三：DP，定义状态DP[i]为总金额为i时最少钱币数，DP[i]=min{DP[i-conis[j]]}+1，时间复杂度O(X*N)
      int coinChange(vector<int>& coins, int amount){
if (coins.empty()) return -1;
vector<int> dp(amount + 1, amount + 2);
dp[0] = 0;
for (int i = 1; i <= amount; ++i){
   for (const int & coin : coins){
       if (i >= coin) {
           dp[i] = min(dp[i], dp[i-coin] + 1);
       }
   }
return dp[amount] > (amount+1) ? -1: dp[amount];//dp[amount]有可能取到的最大值是amount+1，若大于amount说明其仍为初始值，无解
}

  7. 编辑距离
    输入：两个单词word1和word2，限定单词操作有insert、delete、replace，问从word1变成word2至少经过多少步操作

    • 思路一：暴力广搜BFS，每次将word1进行一步操作（若replace、insert，从word1的字符里面挑），若到某步两者相同了，返回（也可让word1和word2两者“双向奔赴”）

    • DP。状态定义：DP[i][j]表示word1前i位和word2前j位的编辑距离。DP[i][j]=DP[i-1][j-1]（word1[i]==word2[j]）或 DP[i][j]=1+min{DP[i-1][j-1],DP[i][j-1],DP[i-1][j]}（word1[i]!=word2[j]） C++版：

      int minDistance(string word1, string word2) {
int m = word1.length(), n = word2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; ++i) {
   for (int j = 0; j <= n; ++j) {
       if (i == 0) {
           dp[i][j] = j;
       } else if (j == 0) {
           dp[i][j] = i;
       } else {
           dp[i][j] = min(
           dp[i-1][j-1] + ((word1[i-1] == word2[j-1])? 0: 1)
           min(dp[i-1][j] + 1, dp[i][j-1] + 1));
       }
   }
}
return dp[m][n];
}

      Python版：

      def minDistance(self, word1, word2):
m, n= len(word1), len(word2)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]#(m,n) matrix
for i in range(m + 1): dp[i][0] =i
for j in range(n + 1):dp[0][j] =j

for i in range(1,m + 1):
   for j in range(1,n + 1):
       dplil[j] = min(
       dp[i-1][j-1] +(0 if word1[i - 1] == word2[j - 1] else 1),
       dp[i-1][j] + 1,
       dp[i][j-1] + 1)
return dp[m][n]

results matching ""

    No results matching ""