LeetCode-动态规划
- 自己理解：
**当前状态是由上一个状态推出来的，那么就会有个动态的过程，就会有一个公式，就是 状态转移公式，对于解题来说，主要的工作 是找到 这个公式，其实也可以说 是找规律（个人理解）**
1. 乘积最大子数组 1\. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空 连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。数组中有正负数。
思路： 有负数就很棘手，数组中若是有两个负数最大值就没那么容易推测了
看下dp值有多少中推测的可能性呢？
- 当前的值
- 当前的值 乘以 上一个dp最大值
- 当前的值是负数时候，乘以上一个dp最小的值（负负得正）
应该还要有一个dp记录最小的值，也许这个最小的值 乘以当前的值 成为正数了
int maxProduct(vector<int>& nums) {
int len = nums.size() + 1;
vector<int> dpmax(len, 0); //用来保存dp最大值
vector<int> dpmin(len, 0); //用来记录dp最小值
dpmin[0] = nums[0];
dpmax[0] = nums[0];
int resMax = nums[0];
for (int i = 1; i < nums.size(); i++) {
//最大值有三种推测方法
dpmax[i] = max(nums[i],max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i]));
//最小值也有三种推测方法
dpmin[i] = min(nums[i]*dpmin[i-1],min(nums[i],dpmax[i-1]*nums[i]));
//都看当前dp值是哪个比较大
int res = max(dpmax[i],dpmin[i]);
resMax = max(resMax,res);
}
return resMax;
}
总结： 当前的转态是由前面转态推出来的，但是这个退的过程有时候是由条件限制的，这个要考虑清楚一些
2. 最大子数组和 2\. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
这题和上个题目一样 ，相对于来说更简单
int maxSubArray(vector<int>& nums) {
if(nums.size() == 1)
return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
int res = dp[0];
for(int i = 1; i < nums.size(); i++)
{
dp[i] = max(nums[i],dp[i-1]+nums[i]); //当前知道dp值可以是上一个dp加上当前nums值或者是当前的nums
res = max(dp[i],res);
}
return res;
}
3. 斐波那契数 3\. 斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
$$
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
$$
给定 n ，请计算 F(n) 。
用个递归可以推出来，但这个用动态解决
思路： 当前状态是由上一个状态推出来的，所以要找出这个转态方程是最为关键的
当前的数是由上两个数推出来的 所以： 转态方程 dp\[i\] = dp\[i - 1\] + dp\[i - 2\]
int fib(int n){
if (n < 2)
return n;
int dp[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
3. 爬楼梯 3\. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路： 假如有3阶楼梯 ，如何求呢？
- 有3阶楼，我从第二阶楼梯上第三节楼梯只有一种方法 – 走一步
- 现在问题转变了 上到第二阶楼梯需要多少步？ 如果我知道上第一阶楼梯是不是也可以求出第二阶楼梯了？
所以可以推出转态方程 ：
dp\[i\] = dp\[i - 1\] + dp\[i - 2\]
其实 和 斐波那契数一样
int climbStairs(int n) {
if (n < 2)
return n;
int dp[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}