有关动态规划问题DP的详细讲解

首先我们要注意，我们学习DP主要是学一种解决问题的思想，而不是一种算法。 动态规划的思想 动态规划是求解多阶段决策过程最优化的方法。 通过把多阶段过程转化为一系列的单阶段问题，利用各阶段之间的关系，逐个求解。 找到各阶段之间的关系是难点。 举个栗子~ 矩阵取数问题 从矩阵的左上走到右下，每次只能向右或者向下走，问怎样走才能使得最后走过路径的和最 大。 分析 当然可以用BFS, DFS去暴力搜索出所有的矩阵，但是暴力完全体现不出任何优美。 如果用的思想，应该怎么做？？ 首先我们想到的一定是贪心策略，每次只能向右或者向下两种选择，那么 是不是只要每次都选择 右面和下面 的中，其元素最大的那个方向，最后的答案就是最大的呢？

用贪心的方法，答案是9. 但是显然有一个更大的答案 10 ，这个答案是如何得出的？ 如果你崇尚暴力的美学，当然也可以把所有的路径搜出来求一个最大值，但是请自行算当N=500时 有多少条路。 我们来用DP的思想来解决这个问题x 设矩阵是 . 假设我们已经知道了最大路径，并且经过（x, y）这个位置，为了从起点到终点得到的和最大，那 么从起点到 (x , y) 经过的数的和也一定要最大。这几乎是显然的。 这是理解这一题的重点。 走到 (x, y) 的上一步，可能是 （x-1, y） 或者（x, y-1）. 按照我门上面得出的结论，我们可以这样说： 如果从起点达到(x,y)的最优路径要经过(x – 1,y)或者(x,y – 1)则，从起点到达(x – 1,y)或者(x,y – 1)的 路径一定也必须是最优的。 所以只需要比较 到达(x – 1,y)或者(x,y – 1)的最优路径哪一个更加优。为了方便表示，我们用：f(x,y) 来表示起点到 （x，y）的最优路径长度。 所以,起点到 （x，y）的最优路径可以表示成：

f(x,y) = max(f(x-1),y),f(x,y-1))+A[x][y];

到了这里肯定会有疑问了，这怎么感觉和上面的贪心策略差不多？？ 其实不，这里是理解DP的重点。根据上面的这个递推公式，我门可以准确的推导出从起点到所有点 的最优解。是整体的最优。而贪心策略只是在局部做选择，是局部的最优。

代码实现如下

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500+10;
int a[MAXN][MAXN];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		cin>>a[i][j];
		
	for(int i=1;i<n;i++)
	{
		a[0][1] += a[0][i-1];
		a[i][0] += a[i-1][0];
	}
	for(int i=1;i<n;i++)
	  for(int j=1;j<n;j++)
	   a[i][j] += max(a[i-1][j],a[i][j-1]);
	
	cout<<a[n-1][n-1]<<endl;
	return 0;
} 

再来个栗子，你来练练手~ 最大字段问题 给出一个整数数组a(正负数都有)，最多有50000个，如何找出一个连续子数组（可以一个都不 取），使得其中的和最大？ 例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。

这个问题的暴力解决方案就是一个双层循环， 时间复杂度，50000个数据一定超时。

for(int i=1;i<=n;i++)
   {
   	  int sum =0;
   	  for(int j=i;i<=n;j++)
   	     {
   	     	sum+=a[j];
   	     	ans = max(anx,sum);
			}
   }

这已经是可以用动态规划思想去考虑的最简单的问题了， 每一步的决策无非就是，是否继续把下一个元素加入当前的子段. 动态规划大显身手。我们开一个数组dp[] , 记录dp[i]表示以a[i]结尾的 全部子段中 最大的那个的 和。 这样我们就可以根据它dp[i] 的正负，去考虑是否把下一个元素加入到当前的子段。 如果dp[i] 是负数，那么我们为什不从a[i+1]新维护一个子段呢？ 如果dp[i] 是正数，那么显然可以继续把a[i+1] 加入到当前的子段。 最后我们只需要找出所有最大子段中，最大的那个。

#include <iostream>
 #include <cmath>
using namespace std; 
const int MAXN = 50000+10; 
long long a[MAXN]; 
int main()
 {     
     int n; 
    long long ans;   
     cin >> n;     
     for (int i = 0; i < n; i++)         cin >> a[i];  ans = a[0];    
      for (int i = 1; i < n; i++)     { if (a[i-1] > 0)     a[i] += a[i-1];    ans = max(ans, a[i]);}           
       cout << ans << endl; 
    return 0; 
    }