【LeetCode学习计划】《算法-入门-C++》第12天动态规划_随笔

【LeetCode学习计划】《算法-入门-C++》第12天动态规划

文章目录

前言
70. 爬楼梯
- 方法1：动态规划 + 滑动数组
- 方法2：通项公式
198. 打家劫舍
- 方法1：动态规划 + 滑动数组
120. 三角形最小路径和
- 方法1：动态规划
- 方法2：动态规划 + 滚动数组

LeetCode【学习计划】：【算法】

前言

动态规划（Dynamic Programming, DP）在算法中是一个大头，它旨在将待求解问题化为若干个子问题。先求解子问题，然后从这些子问题的解得到原问题的解。动态规划中的子问题之间往往是有联系的。

70. 爬楼梯

LeetCode: 70. 爬楼梯

简单 color{#00AF9B}{简单} 简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

方法1：动态规划 + 滑动数组

我们用 f ( x ) f(x) f(x)来表示爬到第x阶台阶时的方案数。这样我们就能得到一个数组dp来存储 x ∈ [ 1 , n ] x in [1, n] x∈[1,n]的 f ( x ) f(x) f(x)，其中n是台阶数。

题目中说我们每次可以爬1或2格台阶，这句话是在从当前台阶往后爬的角度上来说的；反过来，我们考虑当前台阶时怎么到达的，可以发现我们要么从倒数第2格走了2步上来，或者是从前1格走了1步上来。而这句话转化为数学公式如下：

f ( x ) = f ( x − 2 ) + f ( x − 1 ) f(x)=f(x-2)+f(x-1) f(x)=f(x−2)+f(x−1)

到达第x阶的方案数等于第x-2阶的方案数加上第x-1阶的方案数。

同时，上式还是个递推公式，我们考虑一下f(1)和f(2)即可。

f(1)：爬上第1级台阶只有1种方案。
f(2)：要么1步上第一级台阶再1步上来，要么跨2步直接上到第2级台阶。有2种方案。

因此本题的递推公式为：

f ( x ) = { 1 x = 1 2 x = 2 f ( x − 2 ) + f ( x − 1 ) x > 2 f(x) = begin{cases} {1} & {x=1} \ {2} & {x=2} \ {f(x-2)+f(x-1)} & {x>2} end{cases} f(x)=⎩⎪⎨⎪⎧12f(x−2)+f(x−1)x=1x=2x>2

列举一下前几项的值：1,2,3,5,8,13...
可以发现本题的答案正好是斐波那契数列。

最后本题的答案就是答案数组dp的最后一项。我们还可以做一点优化。我们从递推公式可以看出，某一项的值只和它的倒数第一、二项有关，那么我们只要3个变量即可完成推导，就不需要答案数组了，这也是滑动数组的概念：

     [1,2,3]
1 <- [2,3,5] <- 5
2 <- [3,5,8] <- 8

class Solution
{
public:
    int climbStairs(int n)
    {
        if (n == 1)
            return 1;
        else if (n == 2)
            return 2;

        int pre2 = 1, pre = 2;
        int ans = 0;
        for (int _ = 3; _ <= n; _++)
        {
            ans = pre2 + pre;
            pre2 = pre;
            pre = ans;
        }
        return ans;
    }
};

复杂度分析

时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)。我们只需要常量空间来存储若干变量。

参考结果

Accepted
45/45 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 79.65 % of cpp submissions (5.8 MB)

方法2：通项公式

由上文我们已知本题的答案正好符合斐波那契数列，那么我们也可以直接由斐波那契数列的通项公式来计算：
f ( x ) = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] f(x)= frac{1}{sqrt{5}} left[ {left( frac{1+ sqrt{5}}{2} right)}^n - {left( frac{1- sqrt{5}}{2} right)}^n right] f(x)=5 1[(21+5 )n−(21−5 )n]

#include 
class Solution
{
public:
    int climbStairs(int n)
    {
        const double sqrt5 = sqrt(5);
        const double numerator = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);
        return (int)round(numerator / sqrt5);
    }
};

复杂度分析

代码中使用的pow函数的时空复杂度与CPU的指令集相关，这里不作分析。

参考结果

Accepted
45/45 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 25.47 % of cpp submissions (6 MB)

198. 打家劫舍

LeetCode: 198. 打家劫舍

中等 color{#FFB800}{中等} 中等

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

方法1：动态规划 + 滑动数组

我们先设数组dp存放偷到第i家时能偷到的最高金额，接下来就是思考如何计算每到一家的最高金额呢？我们考虑来到第k家时的情况：

偷第k家。那么按照题意就不能偷第k-1家，因此第k家的总金额就是前k-2家的总金额dp[k-2]加上第k家的金额nums[k]。
不偷第k家。那么到达第k家时的总金额就是前k-1家的总金额dp[k-1]。

于是我们就能写出如下的状态转移方程（可以理解为递推公式）：

d p [ i ] = m a x ( d p [ i − 2 ] + n u m s [ i ] , d p [ i − 1 ] ) dp[i]=max(dp[i-2]+nums[i], dp[i-1]) dp[i]=max(dp[i−2]+nums[i],dp[i−1])

其中，dp[0]为第一家的金额nums[0]，dp[1]为第一家和第二家金额的最大值max(nums[0], nums[1])。最终的答案为dp数组的最后一项。

和上题一样，本题的状态转移方程中也是涉及到了3个量：dp[i]，dp[i-1]，dp[i-2]。因此本题也可以用滑动数组的思想，将空间复杂度为 O ( n ) O(n) O(n)的dp数组优化为 O ( 1 ) O(1) O(1)的3个变量。

#include 
using namespace std;
class Solution
{
public:
    int rob(vector &nums)
    {
        const int n = nums.size();
        if (n == 1)
        {
            return nums[0];
        }

        int pre = nums[0];
        int ans = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++)
        {
            int temp = ans;
            ans = max(pre + nums[i], ans);
            pre = temp;
        }

        return ans;
    }
};

复杂度分析

时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)。我们只需要常量空间来存储若干变量。

参考结果

Accepted
68/68 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 47.78 % of cpp submissions (7.5 MB)

120. 三角形最小路径和

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

中等 color{#FFB800}{中等} 中等

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

方法1：动态规划

设dp[level][i]为到达第level层的第i位置时的最小路径和

我们先考虑一下dp[i][j]的值如何计算。由题意：只能从(i-1, j-1)和(i-1, j)来到(i, j)，因此dp[i][j]必然是前两项的最小值加上自身的值，状态转移方程为：
d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) + t r i a n g l e [ i ] [ j ] dp[i][j]=min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] dp[i][j]=min(dp[i−1][j−1],dp[i−1][j])+triangle[i][j]

由于第i层共有i个元素，而第i-1层只有i-1个元素，所以我们还要注意一下边界情况。

当j=0时，不存在(i-1, 0-1)，因此每一层的最左侧结点只能用dp[i-1][j]来计算。
当j=i时，不存在(i-1, i)，因此每一层的最右侧结点只能用dp[i-1][j-1]来计算。

#include 
#include 
using namespace std;
class Solution
{
public:
    int minimumTotal(vector> &triangle)
    {
        const int n = triangle.size();
        vector> dp(n, vector(n));
        dp[0][0] = triangle[0][0];

        for (int i = 1; i < n; i++)
        {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];
            for (int j = 1; j < i; j++)
            {
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        }

        return *min_element(dp[n - 1].begin(), dp[n - 1].end());
    }
};

复杂度分析

时间复杂度： O ( n 2 ) O(n^2) O(n2)
空间复杂度： O ( n 2 ) O(n^2) O(n2)。我们需要一个 n × n n times n n×n的二维数组。

参考结果

Accepted
44/44 cases passed (4 ms)
Your runtime beats 92.18 % of cpp submissions
Your memory usage beats 13.81 % of cpp submissions (8.8 MB)

方法2：动态规划 + 滚动数组

d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) + t r i a n g l e [ i ] [ j ] dp[i][j]=min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] dp[i][j]=min(dp[i−1][j−1],dp[i−1][j])+triangle[i][j]

我们从之前的状态转移方程中可以看出，dp[i]只和它的上一行dp[i-1]有关系，那也就是说我们至少可以把空间复杂度为 O ( n 2 ) O(n^2) O(n2)的dp数组降为 O ( 2 × n ) = O ( n ) O(2 times n)=O(n) O(2×n)=O(n)。

定义一个数组predp，它相当于dp[i-1]。每次往下走一行时，predp记录之前的dp，然后将新的结果存入dp，这样一来就完成了基于滚动数组思想的优化。

#include 
#include 
using namespace std;
class Solution
{
public:
    int minimumTotal(vector> &triangle)
    {
        const int n = triangle.size();
        vector *predp = new vector(1, triangle[0][0]), *dp = predp;

        for (int level = 1; level < n; level++)
        {
            dp = new vector();
            dp->reserve(level + 1);

            dp->emplace_back(predp->at(0) + triangle[level][0]);
            for (int j = 1; j < level; j++)
            {
                dp->emplace_back(min(predp->at(j - 1), predp->at(j)) + triangle[level][j]);
            }
            dp->emplace_back(predp->at(level - 1) + triangle[level][level]);
            delete predp;
            predp = dp;
        }

        return *min_element(dp->begin(), dp->end());
    }
};

复杂度分析

时间复杂度： O ( n 2 ) O(n^2) O(n2)
空间复杂度： O ( n ) O(n) O(n)

参考结果

Accepted
44/44 cases passed (4 ms)
Your runtime beats 92.18 % of cpp submissions
Your memory usage beats 37.89 % of cpp submissions (8.5 MB)

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5635741.html

【LeetCode学习计划】《算法-入门-C++》第12天动态规划

发表评论

评论列表（0条）

【LeetCode学习计划】《算法-入门-C++》第12天 动态规划

发表评论

评论列表（0条）

【LeetCode学习计划】《算法-入门-C++》第12天动态规划