LeetCode【剑指offer】系列（动态规划篇）

剑指offer10-I.斐波那契数列

题目链接

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

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

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

答案需要取模1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回1。

思路：虽然矩阵快速幂也能做，但是这里用动态规划。

通过代码：

class Solution {
public:int fib(int n) {if(n < 2)return n;int mod = 1e9 + 7;int a = 0, b = 1;int res;for(int i = 0; i < n - 1; i++){res = (a + b) % mod;a = b;b = res;}return res;}
};

剑指offer10-II.青蛙跳台阶问题

题目链接

题目：今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有num个小格子，每次可以选择跳一个格子或者两个格子。请返回在训练过程中，学员们共有多少种不同的跳跃方式。

结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

思路：本质上和上一题一样。

通过代码：

class Solution {
public:int trainWays(int num) {if(num < 2)return 1;int mod = 1e9 + 7;int a = 1, b = 1;int res;for(int i = 0; i < num - 1; i++){res = (a + b) % mod;a = b;b = res;}return res;}
};

剑指offer19.正则表达式匹配

题目链接

题目：请设计一个程序来支持用户在文本编辑器中的模糊搜索功能。用户输入内容中可能使用到如下两种通配符：

• '.'匹配任意单个字符。
• '*'匹配零个或多个前面的那一个元素。

请返回用户输入内容 input 所有字符是否可以匹配原文字符串 article。

思路：见Leetcode题解

通过代码：

class Solution {
public:bool articleMatch(string s, string p) {int m = s.size() + 1, n = p.size() + 1;vector<vector<bool>> dp(m, vector<bool> (n, false));dp[0][0] = true;for(int i = 2; i < n; i += 2)dp[0][i] = dp[0][i - 2] && p[i - 1] == '*';for(int i = 1; i < m; i++)for(int j = 1; j < n; j++){if(p[j - 1] == '*')dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && s[i - 1] == p[j - 2] || dp[i - 1][j] && p[j - 2] == '.';elsedp[i][j] = dp[i - 1][j - 1] && s[i - 1] == p[j - 1] || dp[i - 1][j - 1] && p[j - 1] == '.';}return dp[m - 1][n - 1];}
};

剑指offer42.连续子数组的最大和

题目链接

题目：某公司每日销售额记于整数数组sales，请返回所有连续一或多天销售额总和的最大值。

要求实现时间复杂度为O(n)的算法。

思路：dp[i]表示以第i天结尾的子数组的最大和。从第i-1天转移到第i天有两种选择：（1）第i天接在前一段得到最大和为dp[i-1] + sales[i]，（2）第i天单独成段，最大和为sales[i]，二者取较大值完成状态转移即可。最后，遍历过程中用res记录最大值即可。

通过代码：

class Solution {
public:int maxSales(vector<int>& sales) {vector<int> dp(sales.size());dp[0] = sales[0];int res = dp[0];for(int i = 1; i < sales.size(); i++){dp[i] = max(dp[i - 1] + sales[i], sales[i]);res = max(res, dp[i]);}return res;}
};

剑指offer46.把数字翻译成字符串

题目链接

题目：现有一串神秘的密文ciphertext，经调查，密文的特点和规则如下：

• 密文由非负整数组成
• 数字0-25分别对应字母a-z

请根据上述规则将密文ciphertext解密为字母，并返回共有多少种解密结果。

思路：首先需要注意，包含前导0不属于合法密文，即01这种无法解密为字母b。dp[i]表示前i个数字的解密结果种数，对于当前数字s[i-1]，它可以选择单独作为一个密文，也可以选择和s[i-2]合成一个两位数作为密文。合成两位数需要判断其数值范围是否在10-25之间。

通过代码：

class Solution {
public:int crackNumber(int ciphertext) {string s = to_string(ciphertext);vector<int> dp(s.size() + 1);dp[0] = 1;dp[1] = 1;for(int i = 2; i < dp.size(); i++){string alph = s.substr(i - 2, 2);int num = stoi(alph);if(num >= 10 && num <= 25)dp[i] = dp[i - 1] + dp[i - 2];elsedp[i] = dp[i - 1];}return dp[s.size()];}
};

剑指offer47.礼物的最大值

题目链接

题目：现有一个记作二维矩阵frame的珠宝架，其中frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如frame = [[0]]。

思路：dp[i][j]表示走到该位置时的最大价值。要想到达dp[i][j]，只能从上面或者左侧到达，因此，取其二者中的最大值加上当前位置的价值即可。

通过代码：

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int n = frame.size(), m = frame[0].size();vector<vector<int>> dp(n + 1, vector<int> (m + 1));for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];return dp[n][m];}
};

剑指offer60.n个骰子的点数

题目链接

题目：你选择掷出 num 个色子，请返回所有点数总和的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 num 个骰子所能掷出的点数集合中第 i 小的那个的概率。

思路：dp[i][j]表示色子个数为i时第j小的点数的概率，即dp[num]为所需要范围的答案。已知dp[1]的各个点数的概率为1/6，所以对dp[1]进行相应的初始化。已知i-1个色子的概率，需要将状态转移到i个色子。由于多了一个色子，这个色子的点数只能为1-6，且概率分别为1/6。对于dp[i-1][j]，加上多的色子的点数，就是对dp[i]造成的影响。收集这种影响即可完成状态转移。

通过代码：

class Solution {
public:vector<double> statisticsProbability(int num) {vector<vector<double>> dp(num + 1, vector<double> (5 * num + 1));for(int i = 0; i < 6; i++)dp[1][i] = 1.0 / 6.0;for(int i = 2; i <= num; i++){for(int j = 0; j < 5 * (i - 1) + 1; j++){for(int k = 0; k < 6; k++)dp[i][j + k] += dp[i - 1][j] / 6.0;}}return dp[num];}
};

剑指offer62.圆圈中最后剩下的数字

题目链接

题目：社团共有num位成员参与破冰游戏，编号为0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字target，从 0 号成员起开始计数，排在第 target位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

思路：约瑟夫环问题。

通过代码：

class Solution {
public:int iceBreakingGame(int num, int target) {int res = 0;for(int i = 2; i <= num; i++)res = (res + target) % i;return res;}
};