动态规划原理及算法题(1)

admin管理员组

文章数量:1794759

动态规划原理及算法题(1)

1. 第 N 个泰波那契数（easy）

泰波那契数相当于斐波那契数的孪生兄弟，是它的加强版。

1.题目解析

 2.讲解算法原理

如果用动态规划的原理来解决这个问题的话，一般分五步进行

(1) 确定状态表示

动态规划的做题流程一般是先定义一个dp表，dp表一般就是一个一维数组或者是一个二维数组

先定义一个数组，这个数组一般就叫做dp表，然后想办法把这个dp表填满，填满之后里面的某一个值可能就是我们的最终结果。

状态表示就是dp表中某一个值所代表的含义 

状态表示是怎么来的呢？

1，题目要求

2，经验 + 题目要求

3，分析问题的过程中，发现重复子问题，把重复子问题抽象成为状态表示

所以刚开始先练前两个，等到动态规划熟了，进而介绍第三种，第三种就是表示动态规划的方式。

(2)根据状态表示来推导状态转移方程

和(1)一样，不用学术型的语言来表示状态转移方程，我们这里的状态转移方程就是dp[i]等于什么。

(1)和(2)是动态规划中最核心的两步

(3)初始化

初始化的含义就是保证填表的时候不越界。

怎么填表？就是根据状态转移方程来进行填表。

(4)填表顺序

为什么要研究它呢？就是为了填写当前状态的时候，所需要的状态已经计算过了

(5)返回值

返回值就是最终我们想要的结果。结合题目要求 + 状态表示

3.编写代码

动态规划代码的编写是非常固定的四步

1，创建一个dp表

2，在正式的填表之前初始化

3，正式填表

4，确定返回值

因为有n个值，所以要创建一个n + 1的dp表，才能访问到第 n 个值，因为数组的下标是从0开始的。

 解题代码：

class Solution { public:     int tribonacci(int n) {         //处理一下边界问题         if (n == 0 || n == 1)             return n;         if (n == 2)             return 1;         vector<int> a(n + 1);         a[0] = 0, a[1] = a[2] = 1;         for (int i = 3; i <= n; i++)             a[i] = a[i - 1] + a[i - 2] + a[i - 3];         return a[n];     } }

4.空间优化 

关于动态规划空间的优化，一般都用滚动数组。

滚动数组一般用有限个变量来表示的。为了取名方便就给它们起名叫滚动数组。用滚动数组做优化的时候，一定要确定好顺序。 赋值操作一定要确保从前向后赋值。

//滚动数组的写法 class Solution { public:     int tribonacci(int n) {         // 处理一下边界问题         if (n == 0 || n == 1)             return n;         if (n == 2)             return 1;         int a = 0, b = 1, c = 1, d = 0;         for (int i = 3; i <= n; i++) {             d = a + b + c;             a = b, b = c, c = d;         }         return d;     } };

2. 三步问题（easy）

1.题目解析

当小孩在第0格位置的时候，要去第一节台阶，只有1种走法，要想到第二节台阶，可以从第一节台阶走，去第一节的台阶有一种走法，从1到2有一种，也可以从0阶台阶直接到第二节这算一种走法，加起来有两种走法，到第三节的时候，可以从0到3，也可以从1到三，也可以2到3，再加上如何到1、2台阶的方法数，加起来有四种......

2.讲解算法原理

(1) 确定状态表示

dp[i]表示到达 i 位置时，一共有多少种方法。

(2)根据状态表示来推导状态转移方程

以 i 位置的状态，最近的一步来划分问题，dp[i]可以分为三种情况，要么从dp[i - 1]到达dp[i]，要么从dp[i - 2]到达dp[i]，要么从dp[i - 3]到达dp[i]。

那么状态转移方程就有了：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

(3)初始化

dp[0] = 0,dp[1] = 1,dp[2] = 2,dp[3] = 4

(4)填表顺序

从左到右

(5)返回值

1，创建dp表

2，初始化

3，填表

4，确定返回值

//题解 class Solution { public:     int waysToStep(int n) {         const int MOD = 1e9 + 7;         if (n == 0 || n == 1 || n == 2)             return n;         if (n == 3)             return 4;         vector<int> dp(n + 1);         dp[1] = 1, dp[2] = 2, dp[3] = 4;         for (int i = 4; i <= n; i++) {              //因为值很大，所以要对结果取模1e9 + 7             dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;         }         return dp[n];     } };

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-19，如有侵权请联系 cloudcommunity@tencent 删除前往查看数组算法原理dp动态规划

本文标签： 动态规划原理及算法题(1)