动态规划算法

例：

走楼梯，可以一次上一阶，也可以，一次上两阶，根据楼梯的阶数来判断有几种上楼梯的方法。

分析：

f(1) = 1; 1种

f(2) = 2; 2种

f(3) = f(1) + f(2);3种

f(4) = f(3) + f(2) ;5种

…

依次类推

代码如下:

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
#include<iostream>
using namespace std;

int WalkCount(int n)
{
	//可以一次走一阶台阶，也可以一次走两阶台阶
	if (n < 0)
	{
		return  0;
	}
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	else {
		return WalkCount(n-1)+WalkCount(n-2);
	}
}
int main(void)
{
	cout << WalkCount(45) << endl;
	return 0;
}

我们发现，当楼梯结束过大的时，会因为内存消耗过大而发生栈溢出。

因为调用了大量重复的函数，将栈消耗光了。

解决办法:避免重复计算的部分，将重复计算的值保存下来。

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
long long  WalkCount(int n)
{

	long long  ret = 0;
	if (n <= 0)
	{
		return 0;
	}
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	long long * value = new long long[n + 1];//索引从0开始
	value[0] = 0;
	value[1] = 1;
	value[2] = 2;

	for (int i = 3; i <= n; i++)
	{
		value[i] = value[i - 1] + value[i - 2];
	}

	ret = value[n];
	delete value;
	return ret;
}

动态规划算法也是一种分治的思想。

分治算法是把原问题分解为若干子问题，自顶向下，求解子问题，合并子问题的解从而得到原问题的解。

动态规划也是自顶向下把原问题分解为若干子问题，不同的是，然后，自底向上，先求解最小的子问题，把结果存储在表格中，在求解大的子问题时，直接从表格中查询小的子问题的解 ，避免重复计算，从而提高了算法效率。

（就是定义了一个数组存储之前得到的内容，累加到传进来的对应值。）

什么时候使用动态规划算法？

如果要求一个问题的最优解(通常是最大值或者最小值)，而且该问题能能够分解为若干子问题，并且小问题之间也存在 重叠的子问题，则考虑使用动态规划。

怎么使用动态规划？

五部曲

  1. 判断题意是否找出一个问题的最优解。
  2. 从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的问题。
  3. 从下网上分析问题，找出这些问题之间的关联(状态转移方程)。
  4. 讨论底层的边界问题。
  5. 解决问题(通常使用数组进行迭代求出最优解)

练习

给定一根线段，长为n,分成m段，最大的乘积是多少？

例如:长为10，最大分为3*4 *2 = 36

感谢这位老哥分享思路剑指offer–剪绳子（动态规划+贪心算法）详解

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//传进来的是绳子的长度
int CutRope(int n)
{
	int result = 0;
	if (n <= 1)
	{
		return 0;
	}
	if (n == 2)
	{
		return 2;
	}
	if (n == 3)
	{
		return 3;
	}
	//动态开辟数组
	int* temp = new int[n + 1];//数组索引从0开始
	//绳子多长(n多大),对应分割的最大乘积就存在数组对应下标所指向的值temp[n]
	temp[0] = 0;
	temp[1] = 0;
	temp[2] = 2;
	temp[3] = 3;
	/*
	我们不需要去考虑到底要分割成多少段求出来的乘积才是最大的，
	每次分割成都两段，这两段的乘积最大值已经在之前求出来并且存到了temp中对应的位置上了，
	我们只需要对比这几种分割(分成两段的不同情况，这两段最大的乘积都是多少)选出最大的，
	放到该长度n，在temp数组中的位置即可。
	例： 4 可以分为1 3，2 2 ，3 1 
	1、2、3分成的乘积最大值，在之前已经求出来了，最需要分成这两种的乘积即可。
	3 4 3 最大为 4 ，存进temp[4] = 4;
	
	*/
	for (int i = 4; i <= 4; i++)
	{
		int max = 0;//保存当前长度乘积最大的。
		//循环计算出最大的
		for (int j = 1; j <= i / 2; j++)
		{
			if (max < temp[j] * temp[i - j])
			{
				max = temp[j] * temp[i - j];
			}
		}
		temp[n] = max;
	}
	result = temp[n];
	delete temp;
	return  result;
}