LeetCode-动态规划

Last updated on 3 months ago

  • 自己理解：

     **当前状态是由上一个状态推出来的，那么就会有个动态的过程，就会有一个公式，就是 状态转移公式，对于解题来说，主要的工作 是找到 这个公式，其实也可以说 是找规律（个人理解）**

1. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。数组中有正负数。

思路： 有负数就很棘手，数组中若是有两个负数最大值就没那么容易推测了
看下dp值有多少中推测的可能性呢？

  1. 当前的值
  2. 当前的值 乘以 上一个dp最大值
  3. 当前的值是负数时候，乘以上一个dp最小的值（负负得正）

应该还要有一个dp记录最小的值，也许这个最小的值 乘以当前的值 成为正数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

这题和上个题目一样 ，相对于来说更简单

1
2
3
4
5
6
7
8
9
10
11
12
13
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. 斐波那契数

斐波那契数 （通常用 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]

1
2
3
4
5
6
7
8
9
10
11
12
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. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路： 假如有3阶楼梯 ，如何求呢？

  • 有3阶楼，我从第二阶楼梯上第三节楼梯只有一种方法 – 走一步

  • 现在问题转变了 上到第二阶楼梯需要多少步？ 如果我知道上第一阶楼梯是不是也可以求出第二阶楼梯了？

    所以可以推出转态方程 ：

    dp[i] = dp[i - 1] + dp[i - 2]

    其实 和 斐波那契数一样

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
       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];
       }