动态规划算法
例：
走楼梯，可以一次上一阶，也可以，一次上两阶，根据楼梯的阶数来判断有几种上楼梯的方法。
分析：
f(1) = 1; 1种
f(2) = 2; 2种
f(3) = f(1) + f(2);3种
f(4) = f(3) + f(2) ;5种
…
依次类推
代码如下:
#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;
}
我们发现，当楼梯结束过大的时，会因为内存消耗过大而发生栈溢出。
因为调用了大量重复的函数，将栈消耗光了。
解决办法:避免重复计算的部分，将重复计算的值保存下来。
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;
}
动态规划算法也是一种分治的思想。
分治算法是把原问题分解为若干子问题，自顶向下，求解子问题，合并子问题的解从而得到原问题的解。
动态规划也是自顶向下把原问题分解为若干子问题，不同的是，然后，自底向上，先求解最小的子问题，把结果存储在表格中，在求解大的子问题时，直接从表格中查询小的子问题的解 ，避免重复计算，从而提高了算法效率。
（就是定义了一个数组存储之前得到的内容，累加到传进来的对应值。）
什么时候使用动态规划算法？
如果要求一个问题的最优解(通常是最大值或者最小值)，而且该问题能能够分解为若干子问题，并且小问题之间也存在 重叠的子问题，则考虑使用动态规划。
怎么使用动态规划？
五部曲
- 判断题意是否找出一个问题的最优解。
- 从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的问题。
- 从下网上分析问题，找出这些问题之间的关联(状态转移方程)。
- 讨论底层的边界问题。
- 解决问题(通常使用数组进行迭代求出最优解)
练习
给定一根线段，长为n,分成m段，最大的乘积是多少？
例如:长为10，最大分为3*4 *2 = 36
感谢这位老哥分享思路剑指offer–剪绳子（动态规划+贪心算法）详解
//传进来的是绳子的长度
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;
}
