[数据结构与算法]算法基础之动态规划

算法基础之动态规划（C++示例）

动态规划（Dynamic Programming）指的是通过把一个问题递归拆解成更加简单的子问题的方式简化一个复杂问题。在计算机科学中，如果一个问题可以通过先拆解成简单子问题，寻递归找到每个子问题的最优解，这样我们就可以认为这个问题存在最优子结构。

动态规划与分治法的区别是：从分治法的视角来看，每个子问题必须相互独立；但在多轮决策中，这个假设显然不成立，而多轮决策就用到了动态规划方法。

从数学的视角来看，动态规划是一种运筹学方法，是在多轮决策过程中的最优方法。

例1、台阶问题：

有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法？

让f(n)表示走上n级台阶的方法数。

当n为1时，f(n) = 1，n为2时，f(n) =2,就是说当台阶只有一级的时候，方法数是一种，台阶有两级的时候，方法数为2。那么当我们要走上n级台阶，必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步，所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2)，我们用dp[n]来表示动态规划表，dp[i],i>0,i<=n,表示到达i级台阶的方法数。

源码如下：

#include <iostream>
#define N 20        //台阶数为20
using namespace std;
 
int dp[N];          //全局数组，存放决策表
 
int fun(int n)      //返回台阶数为n的走法
{
	if (n == 1 || n == 2)
	{
		return n;
	}
	dp[n-1] = fun(n-1);        //若不为1或2则进行递归计算
	dp[n-2] = fun(n-2);
	dp[n] = dp[n-1]+dp[n-2];   //状态转移方程
	return dp[n];
}
 
int main(int argc,char** argv)
{
	fun(N);
	cout<<dp[15]<<endl;        //输出15阶的走法
	system("pause");
	return 0;
}

例2、最短路径问题：

给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12。

1 3 5 9

8 1 3 4

5 0 6 1

8 8 4 0

分析：对于这个题目，假设m是m行n列的矩阵，那么我们用dp[m][n]来抽象这个问题，dp[i][j]表示的是从原点到i,j位置的最短路径和。我们首先计算第一行和第一列，直接累加即可，那么对于其他位置，要么是从它左边的位置达到，要么是从上边的位置达到，我们取左边和上边的较小值，然后加上当前的路径值，就是达到当前点的最短路径。然后从左到右，从上到下依次计算即可。

源码如下：

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[4][4] = {};     //全局数组，存放决策表
 
int main(int argc,char** argv)
{
	int a[4][4] = {1,3,5,9,8,1,3,4,5,0,6,1,8,8,4,0};  //矩阵存储a[i][j]
	for (int i = 0;i < 4;++i)
	{
		for (int j = 0;j < 4;++j)
		{
			if (i==0 && j==0)                    //边界条件问题需要考虑到
			{
				dp[i][j] = a[i][j];
			}
			else if (i==0 && j!=0)
			{
				dp[i][j] = a[i][j] + dp[i][j-1];
			}
			else if (i!=0 && j==0)
			{
				dp[i][j] = a[i][j] + dp[i-1][j];
			}
			else
			{
				dp[i][j] = a[i][j] + min(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
 
	cout<<"走到位置"<<"(4,4)"<<"最短路径为：";
	cout<<dp[3][3]<<endl;          
 
	return 0;
}