Trluper
0%

动态规划算法思想

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

DP的思想

DP的由来是因为可以将一个问题由子问题得出：完整的问题可以由正方向得出（符合人的逻辑，自底向上），也可以由反方向得出（回溯，自顶向下），一般来说推荐正难则反，即推荐反向思考。

所以dp问题最经典的解题思路四个步骤就是：问题能否从结果往前递归回溯（即由上一个问题得到当前问题解）？-->回溯+记忆化搜索（优化时间）-->1:1翻译成递推，即dp形式-->优化空间

回溯的方式更加容易且贴合dp的子问题递归，因此这里讲的是以反向方式来解决。（不去关心到达怎么解决，只关心当前状态是按什么方程由上一个状态得来的）

记忆化搜索：通过dfs的参数来决定创建的是几维数组，它也决定可了递推式中dp的维度

  • 线性DP：一般从前缀/后缀上进行转移
  • 区间DP：从小区间转移到大区间

1 线性DP

线性DP，一般从前缀/后缀上进行转移。 ### 1.1 背包问题 本质还是选与不选 #### 0-1背包 0-1背包：有n个物品，第i个物品的体积为w[i]，价值为v[i]，每个物品至多选一个，求体积和不超过capacity时的最大价值和。

思路：

背包问题是dp的一个经典题型，涉及到一个当前元素选与不选： - 选：在剩余容量为c-w[i]时，从前i-1个物品得到的最大价值和 - 不选：在剩余容量c时，从前i-1个物品得到的最大价值和 - 取两者较大值。

边界问题： - i<0或者c<0时，需要返回0，次数代表没有其他商品可选，或者没有容量可以装了

记忆化搜索：通过dfs的参数来决定创建的是几维数组，它也决定可了递推式中dp的维度

回溯+记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxValue(vector<int>&w,vector<int>&v,int capacity){
	int n = w.size();
	//数组存储已经得到过的dfs{i,c)
	vector<vector<int>> cache(n,vector<int>(capacity+1,-1));
	function<int(int,int)> dfs = [&](int i,int c){
		if(i < 0||c < 0) return 0;
		int& res = cache[i][c];
		if(res!=-1) return res;
		if(c>=w[i]){
			res = dfs(i-1,c-w[i])+v[i];
		}
		res = max(res,dfs(i-1,c));
		return res;
	};
	return dfs(n-1,capacity);
}
递推

讲上述的“回溯+记忆化搜索”进行1：1翻译可以得到递推，注意翻译过程中的边界条件如何实现（一般通过增加1个开额外的dp数组即可）

上述中，用dp数组得到的递推式如下： dp[i][c] = max(dp[i-1][c],dp[i-1][c-w[i]]+v[i])

1
2
3
4
5
6
7
8
9
10
11
int maxValue(vector<int>&w,vector<int>&v,int capacity){
	int n = w.size();
	vector<vector<int>> dp(n+1,vector<int>(capacity+1,0));	//对边界条件和cache的翻译,i=0作为边界
	for(int i = 0; i < n; ++i){
		for(int j = 1; j <= capacity; ++j){
			if(j>=w[i]) dp[i+1][j] = dp[i][j-w[i]]+v[i];
			dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
		}
	}
	return dp[n][capacity];
}

变体题目：

494.目标和

完全背包

完全背包与01背包的不同点，只在于可以重复选择：

回溯+记忆化搜索

只需要更改res = dfs(i-1,c-w[i])+v[i];为res = dfs(i,c-w[i])+v[i];即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxValue(vector<int>&w,vector<int>&v,int capacity){
	int n = w.size();
	//数组存储已经得到过的dfs{i,c)
	vector<vector<int>> cache(n,vector<int>(capacity+1,-1));
	function<int(int,int)> dfs = [&](int i,int c){
		if(i < 0||c < 0) return 0;
		int& res = cache[i][c];
		if(res!=-1) return res;
		if(c>=w[i]){
			res = dfs(i,c-w[i])+v[i];
		}
		res = max(res,dfs(i-1,c));
		return res;
	};
	return dfs(n-1,capacity);
}

变体题目： 332.零钱兑换

1.2 股票问题(状态DP)

leetcode内由许多股票问题，这类成为状态机DP 121.买卖股票的最佳时机 122.买卖股票的最佳时机Ⅱ 123.买卖股票的最佳时机Ⅲ 188.买卖股票的最佳时机Ⅳ 714.买卖股票的最佳时机含手续费 309.买卖股票的最佳时机含冷冻期

上面的题目均可由回溯+记忆化搜索的一个模板解决。

买卖股票的最佳时机Ⅱ

其题意就是就是至少交易0次，即可以交易无穷次。

回溯+记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxProfit(vector<int>& prices) {
       int n = prices.size();
       vector<vector<int>>cache(n,vector<int>(2,-1));
       function<int(int,bool)>dfs = [&](int i,bool hold){
           if(i<0) return hold?INT_MIN/2:0; 
           int& res = cache[i][hold];
           if(res!=-1) return res;
           if(hold)
               res = max(dfs(i-1,true),dfs(i-1,false)-prices[i]);
           else 
               res = max(dfs(i-1,false),dfs(i-1,true)+prices[i]);
           cache[i][hold] = res;
           return res;
       };
       return dfs(n-1,false);
   }
递推

将回溯+记忆化搜索进行1：1翻译成递推（自底向上），则递推式：dp(i,0)表示前i个股票中当前未持有股票时的最大利润，dp(i,1)`表示前i个股票中当前持有股票时的最大利润，有：

  • dp(i,0) = max(dp(i-1,0),dp(i-1,1)+prices[i])
  • dp(i,1) = max(dp(i-1,1),dp(i-1,0)-prices[i])

边界条件-->即递推的初始状态: 只需要将if(i<0) return hold?INT_MIN/2:0;这句话转换，因此我们为dp多开辟一个空间作为出发临界状态，即dp大小为dp[n+1][2]

  • dp[0][0] = 0
  • dp[0][1] = INT_MIN/2
1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
	int n = prices.size();
	vector<vector<int>> dp(n+1,vector<int>(2,-1));
	dp[0][0] = 0;
	dp[0][1] = INT_MIN/2;
	for(int i = 0;i < n; ++i){
		dp[i+1][0] = max(dp[i][0],dp[i][1]+prices[i]);
		dp[i+1][1] = max(dp[i][1],dp[i][0] - prices[i]);
	}
	return dp[n][0];
}

买卖股票的最佳时机Ⅳ

最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。只需要将上面的代码dfs添加一个参数j即可 ##### 回溯+记忆化搜索 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    int cache[n][k+1][2];
    memset(cache,-1,sizeof(cache));
    function<int(int,int,bool)> dfs = [&](int i,int j,bool hold){
         if(j<0) return INT_MIN/2;
         if(i<0) return hold?INT_MIN/2:0;
         int& res = cache[i][j][hold];
         if(res!=-1) return res;
         if(hold) res = max(dfs(i-1,j,true),dfs(i-1,j,false)-prices[i]);
         else res = max(dfs(i-1,j,false),dfs(i-1,j-1,true)+prices[i]);
         return res;
    };
    return dfs(n-1,k,false);
}

递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 int maxProfit(int k, vector<int>& prices) {
     int n = prices.size();
     int dp[n+1][k+2][2];
     memset(dp,INT_MIN+100000,sizeof(dp));//①这句话就是边界条件返回的翻译
     for(int j = 1;j<=k+1;++j){
         dp[0][j][0] = 0;    //②，①②这两句话就是边界条件返回的翻译
     }
     for(int i = 0; i < n; ++i){
         for(int j = 1; j <= k+1; ++j){
             dp[i+1][j][1] = max(dp[i][j][1],dp[i][j][0]-prices[i]);
             dp[i+1][j][0] = max(dp[i][j][0],dp[i][j-1][1]+prices[i]);
         }
     }
     return dp[n][k+1][0];
}

思考：恰好k次交易如何做，那就需要保证初始状态正好是从恰好0次交易出发，而不会由其他状态，因此只有dp[0][1][0]=0 ，其他均为INT_MIN+100000

买卖股票的最佳时机含冷冻期

直接秒 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(vector<int>& prices) {
    int n =prices.size();
    vector<vector<int>> cache(n,vector<int>(2,-1));
    function<int(int,bool)> dfs = [&](int i,bool hold){
       if(i<0) return hold?INT_MIN/2:0;
        int& res = cache[i][hold];
        if(res!=-1) return res;
        //买入的前一天不能卖出,卖出的前一天没有限制
        if(hold) res = max(dfs(i-1,true),dfs(i-2,false)-prices[i]);
        else res = max(dfs(i-1,false),dfs(i-1,true)+prices[i]);
        return res;
    };
    return dfs(n-1,false);
}

1.3 最长公共子序列

从后缀转移进行转移，即：

回溯+记忆搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(),m = text2.size();
        vector<vector<int>> cache(n,vector<int>(m,-1));
        function<int(int,int)> dfs = [&](int i,int j){
            if(i<0) return 0;
            if(j<0) return 0;
            int& res = cache[i][j];
            if(res!=-1) return res;
            if(text1[i]==text2[j]) res = dfs(i-1,j-1)+1;
            res = max(res,max(dfs(i-1,j),dfs(i,j-1)));
            return res;
        };
        return dfs(n-1,m-1);
    }
};

递推

将上面的回溯+记忆搜索进行1:1翻译， 

1
2
3
4
5
6
7
8
9
10
11
12
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(),n=text2.size();
    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(text1[i]==text2[j]) dp[i+1][j+1] = dp[i][j]+1;
            else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
        }
    }
    return dp[m][n];
}

2 区间DP

  • 区间DP：从小区间转移到大区间，可为两类
    • 选与不选：从两侧向内缩小文体规模--->如最长回文子序列(回文串系列)
    • 枚举选哪个：分割成多个规模更小的子问题--->如多边形三角部分的最低得分

2. 动态规划

我们遇到的问题中，有很大一部分可以用动态规划Dynamic Programming来解。 解决这类问题可以很大地提升你的能力与技巧，我会试着帮助你理解如何使用DP来解题

2.1 动态规划的原理

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度， 因此它比回溯法、暴力法等要快许多。动态规划要求我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。由于单纯使用语言来描述动态规划晦涩难懂，因此采用例子来说明：

问题1：假设有1元、3元和5元的硬币，如何用最少的的硬币凑够11元？

学过贪心算法知道，加如使用贪心算法，每次拿面额最高的银币来逼近这个11是一个方法，但它不能保证一定是最少数量的。因此这里介绍动态规划来解答。正如上面所说，动态规划就是将问题小化，以上一次的子问题的最优解推出下一个的最优解：

  • 因此我们可想当面额为i时，最少的硬币数量是多少，我们使用dp[i]表示凑够i元时最少的硬币数量。
  • 豪无疑问，当i=0时dp[0]=0，因为题目给出了1元、3元和5元的面额，我们需要对这些进行处理，因此能够得到其他的初始条件，i=1时dp[i]=1,i=3时dp[3]=1,i=5时dp[5]=。
  • 完成了初始化条件后，我们可以继续推其他面额的情况，由提供的三种面额，可以知道当i=2时dp[2]=2，但i=3时，组成它的有两种选择，一种时三个1元硬币，另一种是直接选择3元，有min(dp[3].dp[2]+1)知道dp[3]=1是最优解，同样dp[4]，它可以有4=1+3或者4=3+1，两者的的数量是一致的，只不过是次序的不同，再到dp[5]可以检查min(dp[4]+1,dp[2]+1,dp[5])取最小
  • 由上面的分析，我们可以很容易的分析到这样一个状态转移方程： \[ dp[i]= \begin{cases} min(dp[i-1]+1,dp[i-3]+1,dp[i-5]+1),i>5\\ 1,i=1,3,5\\ 2,i=2,4 \end{cases} \]

这样问题就迎刃而解，得如下代码： 

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
/*
* 有面值1，3，5的硬币，试求组成39元时用到最少的硬币数量
* 首先定义dp[i]表示i元时用到得最少银币数
* 由题得初始化条件dp[0]=0,dp[1]=1,dp[3]=1,dp[5]=5
* 当i>5时，会有状态转移方程dp[i]=min(dp[i-1].dp[i-3],do[i-5])+1;
*当i<=5时，这个范围含的2，4未初始化，
*可以增加以判断条件当i-1>=0,i-3>=0,i-5>0来决定，是否要在状态转移方程添加对应项
* 这里由于能够自己推段2，4的最小数量，直接当作初始化，
*/
inline int Min(int a, int b, int c);
int minCoin()
{
	int dp[40];
	dp[0] = 0;
	dp[1] = 1;
	dp[3] = 1;
	dp[5] = 1;	
	dp[2] = 2;
	dp[4] = 2;
	for (int i = 6; i < 40; i++)
	{
		dp[i] = Min(dp[i - 1], dp[i - 3], dp[i - 5]) + 1;
	}
	return dp[39];
}

从上面的案例可以知道，解决动态规划的策略最重要的三步是：

  • 确定dp数组的含义
  • 确定可从题意得出的临界值
  • 确定状态转移方程

有了状态和状态转移方程，问题基本上也就解决了，接下来的问题只是如何写迭代代码而已。

2.2 初级问题

上面的硬币问题只能说是很简单的动态规划问题，我们可以在来看看更复杂一点的。

问题：一个序列有N个数：A[1],A[2],…,A[N]，求出最长连续非降子序列的长度

同样对于这个问题也能使用动态规划来解决，定义一个dp[i]表示包括当前下标i的非降子序列的长度，那么就有这样的条件：

  • 初始条件中，我们肯定可以知道i=0时d[i]=1。
  • 状态转移方程则有d=1+(s[i]>=s[i-1]?d[i-1]:0)，这个状态转移方程指示，我们只需将当前的访问的元素与上一个元素进行对比，如果是>=，则与之前一样是一个非降子序列，反之则不是，重新计数非降子序列长度
  • 最后只需要遍历一次d[i]就能得到最长非降子序列的长度，起始和结束位置也能递推
1
2
3
4
5
6
7
8
9
10
11
12
//时间复杂度为O(n)
inline int maxLength(string s)
{
	int len = s.size();
	vector<int> dp(len);
	dp[0] = 1;
	for (int i = 1; i < len; i++)
	{
		dp[i] =1+( s[i] >= s[i - 1] ? dp[i - 1] : 0);
	}
	return getmaxValue(dp);
}

上面的问题可以进一步升级，不要求连续，如下：

问题：一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度

虽然这个问题不要求连续，我们同样能够使用一维dp[i]尝试解决，同样要找出初始条件和状态转移方程。我们可以让dp[i]是表示在以A[i]结尾的即下标0~i的子序列的最长非降长度，那么就有如下策略：

  • 初始条件dp[0]=1
  • 状态转移方程有两种情况，一是必须在前面找到所有的个x,使得A[i]>=A[x]，更新dp[x]=dp[x]+1,然后执行取最大值,如果没有找到则直接赋值为dp[i]=1。即

\[ dp[i]= \begin{cases} max(dp[x]+1) 当之前序列存在A[i]>=A[x]时，\\ 1， 之前的序列不存在A[x]<=A[i]时 \end{cases} \]

  • 最后遍历一遍dp数组，取最大值，
  • 该算法因为当A[i]<A[i-1]时，需要从后往前遍历dp数组。外部循环为n，内部平均循环为n/2，因此时间复杂度为O(N*N)
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
int maxSonLength(vector<int>& cap)
{
    int len = cap.size();
    if (len == 0)
        return 0;
    vector<int>dp(len);
    dp[0] = 1;
    for (int i = 1; i < len; i++)
    {
            int j;
            vector<int> tmp(i);
            int index=0;
            for (j = i - 1; j >= 0; j--)
            {
                if (cap[i] > cap[j]) {
                    tmp[index]=dp[j];
                    index++;
                }
            }
            int max=getmaxValue(tmp);
            if (max==0)
                dp[i] = 1;
            else
            {
                dp[i]=max+1;
            }
    }
    return getmaxValue(dp);
}

上面的算法分时间复杂度达到了O(N*N),是否有办法使复杂度降到O(NlogN)？我们可以看到上面的程序之所以变为O(N*N)，是因为每次对A[i]都要遍历之前的A[x]，我们是否可以通过增加一个数组来存储形成的最长非降子序列，然后进行二分查找呢，经过二分查找使得复杂度变为O(NlogN):

要这样做我们必须重新定义dp[i]数组的意义，dp[i]它表示长度为i+1的递增子序列中，最大的序列尾数；再定义一个maxL变量，指示当前最长递增子序列的长度，对数组dp二分查找，判断cap[x]要插入的位置

  • 若cap[x]>dp[maxL],表示当前该值比递增子序列的尾数都大，将cap[x]添加到dp尾部，maxL++
  • 若dp[i-1]<cap[x]<dp[i]，更新相应dp[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
int lengthOfLIS(vector<int>& nums,vector<vector<int>>& storage) {
	if (nums.empty())
		return 0;
	vector<int>dp(nums.size());
	int maxL = 0;
	for (auto num : nums)
	{
		int lo = 0, hi = maxL;
		//二分查找
		while (lo < hi)
		{
			int mid = (lo + hi) / 2;
			if (dp[mid] < num)
				lo = mid + 1;
			else
				hi = mid;
		}
		dp[lo] = num;
		if (lo == maxL)
		{
			maxL++;
			if(storage[0].size<maxL)
				storage.clear();
			storage.push_back(dp);
		}
	}
	return maxL;
}

附加：如果要你返回所有最长递增子序列或者返回最长递增子序列的个数该如何解决？ leetcode第673题.最长递增序列的个数

2.3 中级

上面举的例子都是对一维dp来解决，接下来介绍如何解决二维dp的问题。

**问题：平面上有N*M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始， 每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来， 这样下去，你最多能收集到多少个苹果**

当然了，使用动态规划dp就要找初始条件喝状态转移方程

  • 定义二维数组dp[N][M]，d[i][j]表示从A[0][0]到A[i][j]能收集到的最多苹果数量
  • 因为只能向下喝右移动，则有状态转移方程d[i][j]=max(d[i-1][j],d[i][j-1])+A[i][j]，其中i>0,j>0
  • 为了方便实现状态转移方程，我们可以人增加隔离带，即A[0][j]=0、A[i][0]=0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxApple(const vector<vector<int>>& cap)
{
	if (cap.empty())
		return 0;
	int row = cap[0].size(),
		col = cap.size();
	vector<vector<int>> dp(col+1,vector<int>(row+1));
	for (int i = 1; i <= col; i++)
	{
		for (int j = 1; j <= row; j++)
		{
			int Max = max(dp[i - 1][j], dp[i][j - 1]);
			dp[i][j] = Max + cap[i - 1][j - 1];
		}
	}
	return dp[col][row];
}

上述算法复杂度为O(N*M)

参考文章：动态规划：从新手到专家