动态规划练习

【动态规划问题求解步骤】Dynamic Programimng
1、确认原问题与子问题。
2、确认动态规划中间状态。
3、确认边界状态的值。
4、确认状态转移方程。

【例如爬楼梯问题】
问题：一次只能爬1阶或2阶楼梯，求爬上n阶楼梯有多少种爬法？
步骤分析：
1、原问题：求n阶有多少种爬法？
子问题：求1阶台阶、2阶台阶、3阶台阶。。。分别有多少种爬法。
2、记第i个状态为dp[i]，表示爬上i阶台阶的爬法。则我们要求的是dp[n]
3、边界状态为题目给定的初始状态的值，即dp[1]=1,dp[2]=2。
4、状态转移方程：
第i阶可以是从第i-1阶爬1阶转移过来，也可以是从第i-2阶爬2阶转移过来。
则状态转移方程：dp[i] = dp[i-1] + dp[i-2] ;(i>=3)

【例如最优解问题】
问题：从n个数的数组arr[n+1]中(假设从1开始)，取出若干个数两两不相邻的数，求取出的数的最大和是多少？
步骤分析：
1、原问题：n个数取出和最大的最优解
子问题：前1个数的最优解，前2个数的最优解，前3个数的最优解。。。
2、确认中间状态：第i个状态即为前i个数的最优解dp[i]。我们最终要求dp[n]
3、确认边界值：dp[0]=0，dp[1]=前1个数的最优解=arr[1]，dp[2]=前两个房间的最优解=max(dp[1], dp[0]+arr[2])
4、确认状态转移方程：
前i个数的最优解，重点是考虑加不加上第i个数arr[i]，若不加则可以是从dp[i-1]转移过来，若加则只能从dp[i-2]转移过来。
然后再取两种情况的最大值。
dp[i] = max( dp[i-1], dp[i-2]+arr[i] ) ;(i>=2)

【例如连续子数组最大和问题】
问题：在一个数组中有正数有负数，求取出的连续子数组中，最大的和。
步骤分析：
1、原问题：前n个数中连续子数组最大和即最优解。
子问题：以第1个数结尾的最大和，以第2个数结尾的最大和，以第3个数结尾的最大和。。。并用一个变量来更新这些子问题中的最大值，就是原问题结果。
2、确认中间状态：第i个状态，考虑是以第i个数结尾的连续子数组最大和dp[i]。
3、确认边界问题：dp[0]=arr[0],dp[1]=max( arr[1], arr[1]+dp[0] )
4、状态转移方程：
如果前一状态dp[i-1]非正数，那肯定没必要留下前面的，新的状态值就是arr[i],如果dp[i-1]是正数，那就可以加上。关键就在于前面的状态还要不要加上
dp[i]=max( arr[i], arr[i]+dp[i-1] ;(i>=1)

#include<iostream>
#include<vector>

using namespace std;

//保留所有中间状态的写法
int climbStairs(int n)
{
    vector<int> dp(n + 3, 0);   //n+3个元素全部初始化为0。用于记录中间状态dp[i]
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        //状态转移方程，递推关系
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
//优化，节省内存空间，只用两个变量保留前两个中间状态值
int climbStairs2(int n)
{
    
    //两个中间变量值
    int status1 = 1, status2 = 2;
    if (n ==1)
    {
        return status1;
    }
    if (n==2)
    {
        return status2;
    }
    int result = 0;
    for (int i = 3; i <= n; i++)
    {
        //状态转移方程，递推关系
        result = status1 + status2;
        status1 = status2;
        status2 = result;
    }
    return result;
}

int getMax(int a, int b)
{
    return a > b ? a : b;
}
//2、非相邻取数的最大和的最优解
int getBestSum(vector<int>& nums)
{
    int len = nums.size();
    if (len == 0)
    {
        return 0;
    }
    if (len == 1)
    {
        return nums[0];
    }
    //前i个房间的最优解为dp_sum[i-1]，数组从0开始
    vector<int> dp_sum(len, 0);
    dp_sum[0] = nums[0];
    dp_sum[1] = getMax(nums[0], nums[1]);
    for (int i = 2; i < len; i++)
    {
        dp_sum[i] = getMax(dp_sum[i - 1], dp_sum[i - 2] + nums[i]);
    }

    return dp_sum[len - 1];
}

//3、子数组最大和最优解
int maxSubArray(vector<int> &nums)
{
    int len = nums.size();
    if (0 == len)
    {
        return 0;
    }
    //dp[i]表示以第i个元素结尾结尾的连续子数组的和
    vector<int> dp(len, 0);
    dp[0] = nums[0];
    int max_sum = dp[0];
    for (int i = 1; i < len; i++)
    {
        dp[i] = getMax(nums[i], nums[i] + dp[i - 1]);
        if (dp[i] > max_sum)
        {
            //当前状态值替换为最大和
            max_sum = dp[i];
        }
    }
    return max_sum;
}

int main()
{
    int n;
    cout << "please input stairs:";
    cin >> n;
    cout << endl << "methods to the top stairs = " << climbStairs(n) << endl;
    cout << endl << "2methods to the top stairs = " << climbStairs2(n) << endl;
    //注意超过40级台阶以后，可能int表示的32位数字已经不够表示爬台阶的方法数
    //所以最好用 long long表示的64位数字。
    int num = 0;

    //测试非相邻取数的最大和
    //vector<int> nums(5, 0);   //不能这样，否则后面的输入都是追加在5个0后面
    vector<int> nums;   
    cout << "请输入测试非相邻取数的最大和的数组：";
    cin.clear();
    while (cin>>num)
    {
        nums.push_back(num);    //使用push_back()函数的优点就是可以防止数组越界。
    }
    cout << "非相邻取数的最大和=" << getBestSum(nums) << endl;

    //测试连续子数组的最大和
    vector<int> nums1;
    cout << "请输入测试连续子数组的最大和的数组：";
    //下面两句必须组合使用，才能发挥效果，重新输入值
    cin.clear();
    cin.ignore();

    while (cin>>num)
    {
        nums1.push_back(num);
    }
    cout << "连续子数组的最大和=" << maxSubArray(nums1) << endl;
}