动态规划算法

例：

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

分析：

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;
}

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

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

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

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

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

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

怎么使用动态规划？

五部曲

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

练习

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

例如:长为10，最大分为34 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;
}