[TOC]
一、斐波那契数列
剑指 Offer 10- I. 斐波那契数列（简单难度）
509. 斐波那契数（简单难度）
class Solution {
public:
/* 本题是动态规划的经典题目，和509的区别在于答案需要% 1000000007，这是测试数据n最大可取100，防止溢出
F(n)需要由F(n-1)和F(n-2)确定，已知第0和1个，求解第n个
动态规划的步骤：
状态定义：F[n] 表示的含义为斐波那契数列中第 n 个数字
转移方程：F(n)=F(n-1)+F(n−2)，求 n元素时，只需要知道第 n-1 和 n-2个元素即可，故而运算过程中不需要保存全部的dp数组
初始状态： F[0] = 0, F[1] = 1
*/
int fib(int n) {
if(n<=1) return n;
// 动态规划数组
vector<int> dp(2); //dp[i]表示第i个数的斐波那契数值
// 初始状态
dp[0]=0;// 第n-2个数
dp[1]=1;// 第n-1个数
// 遍历[2,n+1)计算第n个数的值
for(int i=2;i<n+1;i++){
int temp = dp[0]+dp[1];//第n个数=第n-2个数+第n-1个数
temp=temp% 1000000007;//取模，防止数字移除
dp[0] = dp[1];//更新第n-2个数
dp[1] = temp;// 更新第n-1个数
}
return dp[1];
}
};
二、爬楼梯问题
剑指 Offer 10- II. 青蛙跳台阶问题（简单难度）
70. 爬楼梯（简单难度）
class Solution {
public:
/* 本题是动态规划的经典题目，和70的区别在于答案需要% 1000000007，这是测试数据n最大可取100，防止溢出
本题和斐波那契数列数列几乎一样，唯一的区别在于初始状态不一样。
第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法
动态规划的步骤：
状态定义：F[n] 表示的含义为上一个n级台阶的跳法数目
转移方程：F(n)=F(n-1)+F(n−2)，求 n+1 元素时，只需要知道第 n 和 n-1 个元素即可，故而运算过程中不需要保存全部的dp数组
初始状态： F[0] = 1, F[1] = 1
*/
int numWays(int n) {
if(n==0) return 1;
if(n==1) return 1;
vector<int> dp={0,0};//爬到第i层楼梯，有dp[i]种方法
dp[0] = 1;
dp[1] = 1;
// 第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法
for(int i=2;i<n+1;i++){
int temp=dp[0]+dp[1];
temp=temp%1000000007;// 防止溢出
dp[0] = dp[1];
dp[1] = temp;
}
return dp[1];
}
};
剑指 Offer 46. 把数字翻译成字符串（中等难度）
class Solution {
public:
/* 解析：这道题定义0-25的数都可以翻译成对应的英文字母，给定一个多位数字，问有多少种方案
存在多种翻译方案的原因在于，每次翻译可以只翻译1个数位，也可以一次性翻译2个数位，例如：
16可以看做1和6分别进行翻译，也可以看做16一次性翻译
这道题可以看做是抽象的爬楼梯问题：给定一个n位数，就是给了n个台阶
每此只能翻译一个数或两个数就是，n个台阶里每此只能上一级或两级
唯一的区别是爬两级需要做一个是否小于26的判断。
【状态定义】：dp[i] 表示的含义为翻译前i个数字的方案数目
【转移方程】：翻译前i位数只能是
（1）第i位数字 无法和前面的数组合，比如 1245, 5 只能单独翻译，那么方法数和 124 是一样的
dp[i]=dp[i-1]，[i-2,i-1]组成的数<10||>25
（2）第i位数字 可以和前面的数组合，比如 1215, 5 可以选择 组合 和 不组合，最终结果为两种情况相加
a. 选择组合，15看成是整体，那么 dp[i] = dp[i - 2]
b. 不选择组合，5单独翻译，那么 dp[i] = dp[i - 1]
最终结果：
dp[i]=dp[i-1]+dp[i−2]，10<=[i-2,i-1]组成的数<=25
*/
int translateNum(int num) {
string numStr=to_string(num);
vector<int> dp={0,0};
dp[0]=1;
dp[1]=1;
// 循环[2,len]，因为dp[i]是定义前i位数字，最后求前len位数字
for(int i=2;i<=numStr.length();i++){
int temp=0;
int digit=(numStr[i-2]-'0')*10+numStr[i-1]-'0';
if(digit>=10&&digit<=25) temp=dp[0]+dp[1];
else temp=dp[1];
dp[0] = dp[1];
dp[1] = temp;
}
return dp[1];
}
};
三、网格路径
剑指 Offer 47. 礼物的最大价值（中等难度）
class Solution {
public:
/* 解析：本类型题是网格路径问题，可以看做是二维版本的爬楼梯问题
【状态定义】：dp[i][j] 表示的含义为从[0,0]到[i-1,j-1]所能获得的最大累积奖励
【转移方程】：[i,j]只能是从上一格[i,j-1]或者左一格[i-1,j]达到
所以dp[i][j]=max(dp[i][j-1],dp[i-1][j])+grid(i-1,j-1);
*/
int maxValue(vector<vector<int>>& grid) {
int row = grid.size();
int column = grid[0].size();
//dp[i][j]表示从grid[0][0]到grid[i-1][j- 1]时的最大价值
vector<vector<int>> dp(row + 1,vector<int>(column + 1,0)) ;
// 遍历[1,1]到[row,column]
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= column; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i-1][j-1];
}
}
return dp[row][column];
}
};
四、序列问题
剑指 Offer 42. 连续子数组的最大和（简单难度）
53. 最大子数组和（简单难度）
class Solution {
public:
/* 本题是动态规划的经典序列题目，数组中的每个元素可能是正数、0或负数，所以不考虑滑动窗口
动态规划的步骤：
【状态定义】：F[i] 表示的含义为以nums[i]结尾的连续子数组最大和（实现时使用动态规划数组dp），0<=i<=n-1
请注意，F[i]并不是nums数组的连续子数组的最大和，其值会随i变化，但是其最大值就是nums数组的连续子数组的最大和
【转移方程】：
假设F(i-1)已知，根据定义新的F(i)=F(i-1)+nums[i]或者F(i)=nums[i];
F(i-1)>0时，F(n)=nums[i]+F(n-1)。F(n-1)产生正向增益，予以于保留
F(i-1)<=0时，F(n)=nums[i]。F(n-1)产生负向增益，不予以于保留，因为非正数+某个数<=某个数
【初始状态】： F[0] = nums[0]
*/
int maxSubArray(vector<int>& nums) {
// 初始化动规数组
vector<int> dp(nums.size(),0);
dp[0]=nums[0];
int res = dp[0];
// 计算[1,n)的最大和
for(int i=1;i<nums.size();i++){
// if(dp[i-1] > 0) dp[i] = nums[i]+dp[i-1];
// else dp[i] = nums[i];
dp[i]=max(nums[i]+dp[i-1],nums[i]);//以nums[i]结尾的连续子数组的最大和
res= max(res,dp[i]);//整个nums数组可以取得的连续子数组的最大和
}
return res;
}
};
五、丑数问题
剑指 Offer 49. 丑数（中等难度）
264. 丑数 II（中等难度）
class Solution {
public:
/* 解析：本类型题是动态规划问题，属于特殊情景类，根据题意设计算法
【状态定义】：dp[i]表示的含义为从小到大排序的第i个丑数
【转移方程】：
理论原理：
最小的丑数是1，即dp[1]=1，那么如何得到其他的丑数呢？
任意一个丑数都是由小于它的某一个丑数*2，*3或者*5得到的，假设存在3个有序数组分别是每个丑数*2，*3或者*5
那么所有丑数的排列，必定就是上面ABC3个有序数组的合并结果然后去重得到的
假设有3个有序数组A={1*2}，B={1*3}，C={1*5}，定义三个指针，p2,p3,p5分别指向其中第一个元素。
dp[2]=min(A[p2],B[p3],C[p5])=2;
A={1*2,2*2}，B={1*3,2*3}，C={1*5,2*5}...
可以发现，ABC三个数组实际上就是dp[]*2，dp[]*3和dp[]*5的结果，
dp[i]=min(A[p2],B[p3],C[p5]),谁的最小就移动谁的指针
合并有序数组的一个比较好的方法，就是每个数组都对应一个指针，
然后比较这些指针所指的数中哪个最小，就将这个数放到结果数组中，然后该指针向后挪一位。
*/
int nthUglyNumber(int n) {
vector<int> dp(n+1,0);//动规数组
dp[1]=1;//初始状态
int p2=1,p3=1,p5=1;//三个指针中的初始值
// 遍历[2,n]
for(int i=2;i<=n;i++){
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = min(min(num2, num3), num5);//取三个有序数组中的最小值
// 谁的最小谁的指针就移动（合并3个有序数组的操作）
if (dp[i] == num2) p2++;
if (dp[i] == num3) p3++;
if (dp[i] == num5) p5++;
}
return dp[n];
}
};
六、约瑟夫环问题
剑指 Offer 62. 圆圈中最后剩下的数字（简单难度）
class Solution {
public:
/* 本题是根据经典的约瑟夫环的数学问题设计而来的，
N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
解决方案：
模拟法：普通的模拟方式就是使用循环链表，按照题意进行模拟，其时间复杂度高达O(nm)
动态规划法：
【状态定义】：dp[i] 表示的含义为有i个数，每次删除第m个数后的剩余数字索引,i<n
【转移方程】：假设有8个数，每次删除第3个数：
索引：0 1 2 3 4 5 6 7
1 2 [3] 4 5 6 7 8
4 5 [6] 7 8 1 2
7 8 [1] 2 4 5
2 4 [5] 7 8
7 8 [2] 4
4 7 [8]
[4]7
7 最终的胜利者
通过观察上述过程，可知，每删除一个数字，相当于将胜利者的索引前移了m位
已知i-1个人时，胜利者的下标位置dp[i-1]
i个人时，胜利者的索引相当于往后移动M位，由于移动后数组可能越界，
如果超出，则超出的部分接到头部，索引则需要对数字个数i取模
dp[i]=(dp[i-1]+m)%i，
【初始状态】： dp[1] = 0
*/
int lastRemaining(int n, int m) {
vector<int> dp(n+1,0);
dp[1]=0;
for (int i = 2; i <=n; i++) {
dp[i]=(dp[i-1]+m)%i;
}
return dp[n];
}
};
七、股票问题
剑指 Offer 63. 股票的最大利润（中等难度）
121. 买卖股票的最佳时机（简单难度）
2016. 增量元素之间的最大差值（简单难度）
class Solution {
public:
/*解析：
股票问题是动态规划的经典应用场景，本题是股票类中最简单的一个问题
买卖一次股票的最大利润意味着必须在股票价格最小值买入，最小值之后的股票价格最大值卖出。
本题只要求出最小值，和最小值之后的最大值就能通过。
但是我们重点放在动态规划的思路上：
【状态定义】：dp[i] 表示的含义为价格数组中0-i的子数组的最大利润,i<n
【转移方程】：假设
前n天的最大利润 = max(前n-1天的最大利润，第n天的价格 - 前n天的最低价格)
dp[i] = max(dp[i-1], min(prices[n], minCost))
【初始状态】： dp[0] = 0
*/
int maxProfit(vector<int>& prices) {
int minCost = INT_MAX;
int res=0;
for(int price:prices){
minCost = min(minCost,price);
res=max(res,price-minCost);
}
return res;
}
};
八、乘积数组
剑指 Offer 66. 构建乘积数组（中等难度）
238. 除自身以外数组的乘积（中等难度）
class Solution {
public:
/*解析：本题的题意不难理解，最简单的思路就是用2个循环暴力破解
但是注意到a的长度最多100000，而且不让用除法，所以暴力破解法大概率会超时。
*/
vector<int> constructArr(vector<int>& a) {
// 方法一：暴力破解法（超时）
// int n=a.size();
// vector<int> res(n,1);
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// if(j!=i) res[i]*=a[j];
// }
// }
// return res;
// 方法二：
int n=a.size();
vector<int> res(n,1);
int left=1;
for(int i=0;i<n;i++){
res[i]=left;
left*=a[i];
}
int right=1;
for(int i=n-1;i>=0;i--){
res[i] *= right;
right *= a[i];
}
return res;
}
};