1. Toy模板网首页
  2. > Toy博客

动态规划（一）一维DP

10月前 作者：HEU_firejef 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了动态规划（一）一维DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

通过上篇文章，动态规划(零)入门概念相信大家已经对动态规划有了一些概念上的理解，那么如何运用动态规划去解决问题呢，首先要知道动态规划的解题步骤。

动态规划的步骤如下：
(1) 设计状态
(2) 写出状态转移方程
(3) 设定初始状态
(4) 执行状态转移
(5) 返回最终的解

下面就通过实战来进入到动态规划的学习当中。

一、爬楼梯

1.1 题目链接

点击跳转到题目位置
相同题目链接(青蛙跳台阶问题)

1.2 题目描述

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

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

1.3 题目代码

class Solution {

public:
    int climbStairs(int n) {
        int dp[n+5];
        memset(dp, 0, sizeof(dp));
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= n; ++i){
            dp[i] = dp[i-1]+dp[i-2];
        }
    return dp[n];
    }
};

1.4 解题思路

(1) 设计状态dp[i]，表示爬到第 i 阶时有多少种方法。

(2) 状态转移方程
d p [ i ] = { 1 , i = 0 1 , i = 1 = d p [ i − 1 ] + d p [ i − 2 ] , i ≥ 2   dp[i] = \begin{cases} 1,\quad i = 0\\ 1,\quad i = 1\\ =dp[i - 1] + dp[i - 2],\quad i \geq2 \end{cases} \ dp[i]=⎩ ⎨ ⎧​1,i=01,i=1=dp[i−1]+dp[i−2],i≥2​ 

因为第0层台阶和第0层台阶肯定就一种可能性。而到了第二层，则是由前两层状态转移过来的。

(3) 初始状态按照状态转移方程来设置即可。

(4) 执行状态转移则是用循环执行i ≥ 2 \geq 2 ≥2的部分。

(5) 返回最终的解就是返回dp[n]。

二、斐波那契数

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

2.3 题目代码

class Solution {
public:
    int fib(int n) {
        int dp[n + 2];
        memset(dp, 0, sizeof(dp));
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i <= n; ++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
    return dp[n];
    }
};

2.4 解题思路

(1) 状态转移方式，设计的状态与爬楼梯一致，详情可参考爬楼梯的题解。

三、 第 N 个泰波那契数

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

3.3 解题代码

class Solution {
public:
    int tribonacci(int n) {
        int dp[40];
        memset(dp, 0, sizeof(dp));
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; ++i){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
    return dp[n];
    }
};

3.4 解题思路

(1) 设计状态dp[i]，表示爬到第 i 阶时有多少种方法。

(2) 状态转移方程
d p [ i ] = { 0 , i = 0 1 , i = 1 1 , i = 2 = d p [ i − 1 ] + d p [ i − 2 ] , i ≥ 3   dp[i] = \begin{cases} 0,\quad i = 0\\ 1,\quad i = 1\\ 1,\quad i = 2\\ =dp[i - 1] + dp[i - 2],\quad i \geq3 \end{cases} \ dp[i]=⎩ ⎨ ⎧​0,i=01,i=11,i=2=dp[i−1]+dp[i−2],i≥3​ 

状态转移方程题目中已经给出公式

(3) 初始状态按照状态转移方程来设置即可。

(4) 执行状态转移则是用循环执行i ≥ 3 \geq 3 ≥3的部分。

(5) 返回最终的解就是返回dp[n]。

四、使用最小花费爬楼梯

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

4.3 解题代码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int dp[n+1];
        memset(dp, 0, sizeof(dp));
        dp[0] = 0;
        dp[1] = 0; 
        for(int i = 2; i <= n; ++i){
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
    return dp[n];
    }
};

4.4 解题思路

(1) 设计状态dp[i]，表示爬到第i层的最小费用。

(2) 状态转移方程
d p [ i ] = { 0 , i = 0 1 , i = 0 1 , i = 2 = m i n ( d p [ i − 1 ] + c o s t [ i − 1 ] , d p [ i − 2 ] + c o s t [ i − 2 ] ) , i ≥ 2   dp[i] = \begin{cases} 0,\quad i = 0\\ 1,\quad i = 0\\ 1,\quad i = 2\\ = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]), \quad i \geq2 \end{cases} \ dp[i]=⎩ ⎨ ⎧​0,i=01,i=01,i=2=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2]),i≥2​ 
一开始出发的第0层和第1层，所以为0层，大于等于2层的费用是由低于两层的费用加上从当层爬上来的费用转移过来的。

(3) 初始状态按照状态转移方程来设置即可。

(4) 执行状态转移则是用循环执行i ≥ 2 \geq 2 ≥2的部分。

(5) 返回最终的解就是返回dp[n]。

五、打家劫舍

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

5.3 解题代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int dp[n+1];
        memset(dp, 0, sizeof(dp));
        if(n == 1){
            return nums[0];
        }
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n; ++i){
            dp[i] = max(nums[i] + dp[i-2], dp[i-1]);
        }
    return dp[n-1];
    }
};

5.4 解题思路

(1) 设计状态dp[i]，表示偷取编号0~i的房子，最大能偷多少。

(2) 状态转移方程
d p [ i ] = { n u m s [ 0 ] , i = 0 m a x ( n u m s [ 0 ] ， n u m s [ 1 ] ) , i = 1 = m i n ( n u m s [ i ] + d p [ i − 2 ] , d p [ i − 1 ] ) , i ≥ 2   dp[i] = \begin{cases} nums[0],\quad i = 0\\ max(nums[0]，nums[1]),\quad i = 1\\ = min(nums[i] + dp[i-2], dp[i - 1]), \quad i \geq2 \end{cases} \ dp[i]=⎩ ⎨ ⎧​nums[0],i=0max(nums[0]，nums[1]),i=1=min(nums[i]+dp[i−2],dp[i−1]),i≥2​ 
一开始只偷取标号为0的房子，那就只有一种可能性。
如果偷取标号0和1的房子，那么就只有偷取0号房子或者偷取1号房子。
如果偷取标号大于等于2的房子，那么就有两种可能性，一种是偷取当前标号的房子，一个是不偷去。

(3) 初始状态按照状态转移方程来设置即可。

(4) 执行状态转移则是用循环执行i ≥ 2 \geq 2 ≥2的部分。

(5) 返回最终的解就是返回dp[n-1]。(n 等于 1的时候例外，因为n == 1的情况下无法初始化状态，直接返回nums[0]即可）

六、删除并获得点数

6.1 题目链接

点击跳转到题目位置

6.2 题目描述

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

6.3 解题代码

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        if(n == 1){
            return nums[0];
        }
        int hash[10010];
        int max0 = 0;
        memset(hash, 0, sizeof(hash));
        for(int i = 0; i < n; ++i){
            max0 = max(nums[i], max0);
            hash[nums[i]] += nums[i]; 
        }
        int dp[10010];
        memset(dp, 0, sizeof(dp));
        dp[0] = 0;
        dp[1] = hash[1];
        for(int i = 2; i <= max0; ++i){
            dp[i] = max(dp[i-2] + hash[i], dp[i-1]);
        }
    return dp[max0];
    }
};

6.4 解题思路

(1) 用哈希表记录从0到最大值的点数和为多少，比如数组中有10个1，那么hash[1] = 10。

(2) 后续思路与打家劫舍一致，没有变化。

七、统计构造好字符串的方案数

7.1 题目链接

点击跳转到题目位置

7,2 题目描述

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

  • 将 ‘0’ 在字符串末尾添加 zero 次。
  • 将 ‘1’ 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

7.3 解题代码

class Solution {
    int mod = 10e8 + 7;
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        int dp[high+1];
        memset(dp, 0, sizeof(dp));
        dp[zero]++;
        dp[one]++;
        int res = 0;
        for(int i = min(zero, one); i <= high; ++i){
            if(i - zero >= 0){
                dp[i] = (dp[i] + dp[i - zero]) % mod;
            }
            if(i - one >= 0){
                dp[i] = (dp[i] + dp[i - one]) % mod;
            }
        }
        for(int i = low; i <= high; ++i){
            res = (res + dp[i]) % mod;
        }
    return res;
    }
};

7.4 解题思路

(1) 解题思路与爬楼梯一致。

(2) 为数不多的差距就是状态是由长度为i - 1和i - 2转移过来的变成了由i - zero， i - one转移过来的。

八、解决智力问题

8.1 题目链接

点击跳转到题目位置

8.2 题目描述

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

  • 比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
    (1) 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
    (2) 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的 最高 分数。

8.3 解题代码

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();
        long long dp[200010];
        memset(dp,0,sizeof(dp));
        for(int i = n-1; i >= 0; --i){
            if(i == n-1){
                dp[i] = questions[i][0];            
                continue;
            }
            int points = questions[i][0];
            int brainpower = questions[i][1];
            dp[i] = max(dp[i+1], points + dp[min(n, i + brainpower + 1)]);
        }
    return dp[0];
    }
};

8.4 解题思路

(1) 设计状态dp[i]，表示解决i ~ n-1号题目的最大分。

(2) 状态转移方程
d p [ i ] = { q u e s t i o n s [ i ] [ 0 ] , i = n − 1 m a x ( d p [ i + 1 ] , d p [ i + b r a i n p o w e r + 1 ] + p o i n t s ) , i ≤ n − 2   dp[i] = \begin{cases} questions[i][0],\quad i = n - 1\\ max(dp[i + 1],dp[i + brainpower + 1] + points), \quad i \leq n - 2\\ \end{cases} \ dp[i]={questions[i][0],i=n−1max(dp[i+1],dp[i+brainpower+1]+points),i≤n−2​ 
初始化从n - 1开始，然后一直倒序遍历即可。

(3) 初始状态按照状态转移方程来设置即可。

(4) 执行状态转移则是用循环执行i ≤ n − 2 \leq n - 2 ≤n−2的部分。

(5) 返回最终的解就是返回dp[0]。

九、解码方法

9.1 题目链接

点击跳转到题目位置

9.2 题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：

  • “AAJF” ，将消息分组为 (1 1 10 6)
  • “KJF” ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

9.3 解题代码

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        int dp[105];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; ++i){
            if(i == 0){
                dp[i] = (s[i] == '0') ? 0 : 1;
            } else{
                if(s[i] != '0'){
                    dp[i] = dp[i-1];
                }
                if((s[i-1] == '1' || s[i-1] == '2')){
                    int val = (s[i-1] - '0') * 10 + (s[i] - '0');
                    if(val <= 26){
                        if(i == 1){   
                            dp[i]++;
                        }
                        else{
                            dp[i] += dp[i-2];
                        }
                    }
                }
            }
        }
    return dp[n-1];
    }
};

9.4 解题思路

(1) 设计状态dp[i]，表示到第i个字符所能表示解码种数。

(2) 状态转移方程
d p [ i ] = { 1 , i = 0 并且 s [ i ] = ′ 0 ′ 0 , i = 1 并且 s [ i ] = ′ 1 ′ 此时需要分类讨论情况了如果 s [ i ] 不为 0 的话，此时 d p [ i ] 先赋值给 d p [ i − 1 ] 。然后讨论配合前面一个字符能否解码 i ≥ 1   dp[i] = \begin{cases} 1,\quad i = 0 并且 s[i] = '0'\\ 0,\quad i = 1 并且 s[i] = '1'\\ 此时需要分类讨论情况了 如果s[i]不为0的话，此时dp[i]先赋值给dp[i-1]。然后讨论配合前面一个字符能否解码i \geq 1\\ \end{cases} \ dp[i]=⎩ ⎨ ⎧​1,i=0并且s[i]=′0′0,i=1并且s[i]=′1′此时需要分类讨论情况了如果s[i]不为0的话，此时dp[i]先赋值给dp[i−1]。然后讨论配合前面一个字符能否解码i≥1​ 
初始化从0开始，然后循环往后即可。

(3) 初始状态按照状态转移方程来设置即可。

(4) 执行状态转移则是用循环执行i ≥ 1 \geq 1 ≥1的部分。

(5) 返回最终的解就是返回dp[n-1]。

十、连续数列

10.1 题目链接

点击跳转到题目位置

10.2 题目描述

给定一个整数数组，找出总和最大的连续数列，并返回总和。

10.3 解题代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp[n+5];
        memset(dp, 0, sizeof(dp));
        int max0 = INT_MIN;
        for(int i = 0; i < n; ++i){
            if(i == 0){
                dp[i] = nums[0];
            } else{
                dp[i] = max(nums[i], dp[i-1] + nums[i]);
            }
            max0 = max(dp[i], max0);
        }
    return max0;
    }
};

10.4 解题思路

(1) 相对基础的一维DP问题，dp[i]表示为选取nums[i]的最大连续数列为多少。

(2) 状态转移方程为
d p [ i ] = { n u m s [ 0 ] , i = 0 m a x ( n u m s [ i ] , d p [ i − 1 ] + n u m s [ i ] ) , i ≥ 1   dp[i] = \begin{cases} nums[0],\quad i = 0\\ max(nums[i], dp[i-1] + nums[i]), \quad i \geq 1\\ \end{cases}\\ \ dp[i]={nums[0],i=0max(nums[i],dp[i−1]+nums[i]),i≥1​ 

(3) 初始状态按照状态转移方程来设置即可

(4) 执行状态转移方程一层循环即可。

(5) 最终解是dp[i]的最大值。

总结

本篇文章通过十道例题，带领读者理解一维DP的一些比较基础的问题，读者可以根据自身实际情况，选取LeetCode上的其他情况进行练习。文章来源地址https://www.toymoban.com/news/detail-471527.html

到了这里，关于动态规划（一）一维DP的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • class066 一维动态规划【算法】

    class066 一维动态规划【算法】

    算法讲解066【必备】从递归入手一维动态规划 // 斐波那契数 // 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 // 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。 // 也就是：F(0) = 0，F(1) = 1 // F(n) = F(n - 1) + F(n - 2)，其中 n 1 // 给定 n ，请计算

    2024年02月04日
    浏览(34)
  • 一维动态规划经典力扣题目（一）

    一维动态规划经典力扣题目（一）

    目录 题一：斐波那契数列 题目二：最低票价 题三：解码方法 递归方法是2的n次方的时间复杂度。 递归代码： 带有缓存的递归，会使时间复杂度得到大幅度优化。 时间复杂度为O(n)。 缓存即记录中间值         优化的方法：         代码：         代码：

    2024年02月21日
    浏览(42)

  • 【leetcode刷题之路】面试经典150题（8）——位运算+数学+一维动态规划+多维动态规划

    20 位运算 20.1 【位运算】二进制求和 题目地址：https://leetcode.cn/problems/add-binary/description/?envType=study-plan-v2envId=top-interview-150   按位逆序运算。 20.2 【位运算】颠倒二进制位 题目地址：https://leetcode.cn/problems/reverse-bits/description/?envType=study-plan-v2envId=top-interview-150   详见代码

    2024年04月16日
    浏览(75)
  • 动态规划(DP)入门——线性DP

    动态规划(DP)入门——线性DP

    在了解线性DP之前，我们首先要知道什么是动态规划，即为将一种复杂问题，分解成很多重叠的子问题，并通过子问题的解得到整个问题的解的算法。听起来比较抽象，动态规划简单来说就是确定问题的状态，通常题目都会提示，一般为“到第i个为止，xx为j(xx为k)的方案数/最

    2024年02月19日
    浏览(48)

  • 「程序员必须掌握的算法」动态规划「上篇」

    动态规划 (Dynamic Programming) 是一种算法思想，用于解决一些复杂的问题。本文将介绍动态规划的分类、概念和经典例题讲解。 动态规划可以分为以下两种类型： 0/1背包问题：该问题是动态规划的一种基本类型。在背包问题中，有n个物品可以放入容量为W的背包中，每个物品有

    2024年02月07日
    浏览(56)
  • 动态规划报告（树形DP+概率DP

    动态规划报告（树形DP+概率DP

    树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。一般需要在遍历树的同时维护所需的信息 以一道题目为例 2022CCPC桂林站G Group Homework No, we don’t want group homework. It’s the place where 1+11 can be true. However, you are currently the leader of a group with three

    2024年02月12日
    浏览(47)
  • 从二维数组到一维数组——探索01背包问题的动态规划优化

    从二维数组到一维数组——探索01背包问题的动态规划优化

    本文将继续上一篇博客爬楼梯之后继续讲解同样用到了动态规划的 01背包问题 在解决动态规划问题时，我们经常面临着空间复杂度的挑战。01背包问题是一个典型的例子，通常使用二维数组来表示状态转移，但这样会带来额外的空间开销。在本文中，我们将探讨如何通过优化

    2024年04月11日
    浏览(60)

  • 一文刷题学懂（一维动态规划）——java+python——3/5

    给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释

    2024年03月23日
    浏览(33)

  • 一文刷题学懂（一维动态规划）——java+python——4/5

    给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 输入：coins = [1, 2, 5], amount = 11 输出

    2024年04月25日
    浏览(40)

  • 【leetcode100-086到090】【动态规划】一维五题合集2

    【单词拆分】 给你一个字符串  s  和一个字符串列表  wordDict  作为字典。如果可以利用字典中出现的一个或多个单词拼接出  s  则返回  true 。 注意： 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 思路： 首先，我们依次考虑s的前i个字母能否被

    2024年02月19日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包