动态规划

题目

http://www.sohu.com/a/153858619_466939
这里有一个漫画，解释的很清楚，算是比较好的动态规划算法入门资料了。
里面有两道经典的习题，爬梯子和挖金矿。分别是一维和二维的情况。

动态规划的三要素：

1. 最优子结构
2. 状态转换方程
3. 边界条件

对应的算法有以下几种：

1. 暴力法，一般时间复杂度较高
2. 递归的方法（算法树），复杂度一般是O(2^n)
3. 备忘录的方法 时空都是O(n)
4. 自底向上填表，空间复杂度O(1)

leetcode上对应的几题：
746Min Cost Climbing Stairs：在爬梯子的基础上变了一下，加了cost，思想不变。

121: Best Time to Buy and Sell Stock : 这里需要注意思路，先找最小值和最大值相减是错的。先找最小值在最小值后面找最大值也是错的。比如2,4,1。
70：爬梯子
53：Maximum Subarray：找到数组中和最大的子串，转换公式：maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];

代码

121

class Solution {
public:
int maxProfit(vector<int>& prices) {
    if(prices.size()==0) return 0;
    int min=prices[0];int maxProfit=0;
    int i=0;
    for( i=0;i<prices.size();i++)
    {
        if(min>prices[i]){
            min=prices[i];
        }
        if(maxProfit<prices[i]-min)
            maxProfit=prices[i]-min;
    }

     return maxProfit;
    
}
};
//注意思路，先找最小值和最大值相减是错的。先找最小值在最小值后面找最大值也是错的。比如2,4,1
//这是动态规划问题吗？ 参考solution的评论
//

70

class Solution {
public:
int climbStairs(int n) {
    vector<int> f(n);
    f[0]=1;f[1]=2;
    for(int i=2;i<n;i++)
    {
        f[i]=f[i-1]+f[i-2];
    }
    return f[n-1];
    
}
};

53

class Solution {
public:
int maxSubArray(vector& nums) {
vector dp(nums.size());
dp[0]=nums[0];
int maxValue=dp[0];
for(int i=1;i<nums.size();i++)
{
dp[i]= nums[i]+(dp[i-1]>0 ? dp[i-1]:0);//(nums[i]>0 ? (dp[i-1]+nums[i]): (nums[i]);
// dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
maxValue=max(dp[i],maxValue);
}
return maxValue;

}

};