算法复习-动态规划（3）

LeetCode No.120 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

回溯法

走路(i,j){
     min(走路(i+1,j),走路(i+1,j+1))

  }

贪心法
如果只看当前层，那么后面层的时候如果有过大的话就没办法了
例如
```
[
     [2],
    [3,4],
   [6,5,7],
  [4,1=>1000,8=>8000,3]
]
```
贪心法：2+3+5+1 =>2+3+5+1000 错！

动态规划
第一步是递归+记忆法=>递推。递归在第一个方法中有大概说了一下。那么接下来的状态变量如何寻找和定义? 我们先从自上而下的去查找，会发现可能性很多，需要穷举（时间复杂度太高了）,底部的可能性太多了,自底而上的话最后指向的顶点只有一个。
状态定义:dp[i][j] 从底走到点(i,j)的路径和最小值
动态方程 dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+Triangle[i,j]
优化子结构:dp[n]就够了，只需要三角形那一行的数据就可以了

代码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp=triangle[triangle.size()-1];  
       //对dp进行赋值，将最后三角形最后一行的值赋值
        for(int i=triangle.size()-2;i>=0;i--)  //剔除掉最后一行，从倒数第二行开始
        {
            for(int j=0;j<triangle[i].size();j++)
              //dp为二维数组的时候
             // dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
              //比较两者有什么差别
                dp[j]=triangle[i][j]+min(dp[j],dp[j+1]);  //优化后
            
        }
        return dp[0];    
    }
};

LeetCode No.152 乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

回溯法+记忆化
动态规划
状态定义:
最简单的定义———dp[i] 表示0走到i位置的最大连续乘积子序列
那么最后的求解的是dp[n-1]
状态转移方程: dp[i+1]=dp[i]*a[i+1](正?负?)
错误！存在一个负负得正的情况同时还有为0的情况，同时还有一种可以不进行相乘操作（换而言之就是乘积之后的结果比a[i]还要小）
状态变量：dp[i][2] 其中第二维：0:max 1:min
状态转移方程:
```
dp[i][0]=max(dp[i-1][0]*a[i],a[i])   (a[i]>=0)
dp[i][0]=max(dp[i-1][1]*a[i],a[i])   (a[i]<0)

dp[i][1]=min(dp[i-1][1]*a[i],a[i])   (a[i]>=0)
dp[i][1]=min(dp[i=1][0]*a[i],a[i])   (a[i]<0)
```
代码

class Solution {
public:
int maxProduct(vector& nums) {
if(nums.size()==1)
return nums[0];
int dp[2][2],result=nums[0];
dp[0][0]=nums[0];
dp[0][1]=nums[0];
for(int i=1;i<nums.size();i++)
{
int x=i%2;
if(nums[i]>=0)
{
dp[x][0]=max(dp[!x][0]*nums[i],nums[i]);
dp[x][1]=min(dp[!x][1]*nums[i],nums[i]);

        }else
        {
            dp[x][0]=max(dp[!x][1]*nums[i],nums[i]);
            dp[x][1]=min(dp[!x][0]*nums[i],nums[i]);
        }
        result=max(result,dp[x][0]);
    }
    return result;
}

};