剑指offer 动态规划篇

题目由入门往上递增

入门

斐波那契数列_牛客题霸_牛客网 (nowcoder.com)

动态规划甚至于算法的入门题目

方法一：按照斐波那契的公式fn=fn-1+fn-2，从1-n求出结果。

class Solution {
public:int Fibonacci(int n) {vector<int>f={0,1,1};for(int i=3;i<=n;i++)f.push_back(f[i-1]+f[i-2]);return f[n];}
};

方法二：按照公式倒推，即用递归求出。

class Solution {
public:int Fibonacci(int n) {if(n==1||n==2) return 1;return Fibonacci(n-1)+Fibonacci(n-2);}
};

简单

连续子数组的最大和_牛客题霸_牛客网 (nowcoder.com)

我们令dp[i]是以第i个数为结尾的子数组和的最大值。如果dp[i-1]为负，则以i-1为结尾的子数组和都为负，因此以dp[i]结果就是第i个数的值，除此之外是dp[i-1]+第i个数。

因此转移公式得出

验证：假设以i为结尾的子数组和的最大值是r到l，则以r-1为结尾的子数组和一定为负数，和我们的推导符合。

class Solution {public:int FindGreatestSumOfSubArray(vector<int> array) {int sum=0;int maxx=array[0];sum=array[0];for(int i=1;i<array.size();i++){sum=max(sum+array[i],array[i]);maxx=max(sum,maxx);}return maxx;}
};

跳台阶_牛客题霸_牛客网 (nowcoder.com)

台阶n可以由n-1跳一步或n-2跳一步得到，因此就是斐波那契数列。.

class Solution {
public:int jumpFloor(int number) {if(number==1) return 1;if(number==2) return 2;return jumpFloor(number-1)+jumpFloor(number-2);}
};

跳台阶扩展问题_牛客题霸_牛客网 (nowcoder.com)

和上一题类似，只不过通项公式变为了fn=fn-1+……f1，求fn

因此这时候我们考虑高斯消元……

开个玩笑，上述公式可以变化为fn=fn-1*2；

问题解决

class Solution {
public:int jumpFloorII(int number) {if (number==1) {return 1;}return jumpFloorII(number-1)*2;}
};

买卖股票的最好时机(一)_牛客题霸_牛客网 (nowcoder.com)

因为只能买卖一次，如果在第k天卖出，就是要求第k天前最小值的买入

也可以dp，太麻烦了没必要。

class Solution {
public:int maxProfit(vector<int>& prices) {int ans=0;int minn=prices[0];for(int i=1;i<prices.size();i++){minn=min(minn,prices[i]);ans=max(prices[i]-minn,ans);}return ans;}
};

中等

连续子数组的最大和(二)_牛客题霸_牛客网 (nowcoder.com)

对于dp方面思路同上，此时只是需要在sum小于0的时候更新l1，在maxx更新的时候维护l和r（l为l1，r为i）

class Solution {public:vector<int> FindGreatestSumOfSubArray(vector<int>& array) {int sum = 0;int maxx = array[0];int l=0,r=0,l1=0;sum = array[0];for (int i = 1; i < array.size(); i++) {if(sum<0){l1=i;}sum = max(sum + array[i], array[i]);if(maxx<=sum){l=l1;r=i;}maxx = max(sum, maxx);}vector<int>ans;for(int i=l;i<=r;i++){ans.push_back(array[i]);}return ans;}
};

矩形覆盖_牛客题霸_牛客网 (nowcoder.com)

通过观察可以得出构成方式只有一竖和两横两种情况，因此有n块肯定是n-1加上一块竖的或者n-2加上两条横的（此时两条竖的已经被上一种情况包含了），因此是斐波那契数列

class Solution {
public:int rectCover(int number) {if(number==0) return 0;if(number==1)return 1;if(number==2) return 2;return rectCover(number-1)+rectCover(number-2);}
};

礼物的最大价值_牛客题霸_牛客网 (nowcoder.com)

最后一格的最大值是它左边和上面的最大值的较大值加上自己，因而只能往右和往下，所以保证了每个格子只会被走一次，无后效性。

此时注意最上面和最左边只有一种走法，可以扩大一格dp数组或者预处理。

class Solution {
public:int maxValue(vector<vector<int> >& grid) {int dp[202][202];dp[0][0]=grid[0][0];for(int j=1;j<grid[0].size();j++){dp[0][j]=grid[0][j]+dp[0][j-1];}for(int j=1;j<grid.size();j++){dp[j][0]=grid[j][0]+dp[j-1][0];}for(int i=1;i<grid.size();i++){for(int j=1;j<grid[0].size();j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];cout<<dp[i][j]<<" ";}}return dp[grid.size()-1][grid[0].size()-1];}
};

最长不含重复字符的子字符串_牛客题霸_牛客网 (nowcoder.com)

设置滑动窗口，记录窗口内的字符，如果下一个进来会重复，就将l往后移直到不重复。记录窗口最大值。

class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> a(128,0);int l=0,r=0,len=s.size();int ans=0;while(r<len){int temp=s[r];while(a[temp]==1){int x=s[l];a[x]--;l++;}a[temp]++;cout<<temp<<" "<<a[temp]<<" "<<r-l<<"\n";ans=max(ans,r-l+1);r++;}return ans;}
};

把数字翻译成字符串_牛客题霸_牛客网 (nowcoder.com)

这题比较烦躁的是要判断一堆乱七八糟无解的情况，反正特判一下。

存在多种编码的情况就是12、26这种，既可以拆分也可以合并。因为字母编码最长为两位，所以dpi的结果是dpi-1加一位或者dpi-2加两位（此时要判断是否合法）因此就是dpi-1+dpi-2。

class Solution {
public:int solve(string nums) {if(nums=="0")return 0; vector<int>ans(100,0);ans[0]=1;if((nums[0]=='1'&&nums[1]!='0')||(nums[0]=='2'&&nums[1]<='6'&&nums[1]>'0')) ans[1]=2;else ans[1]=1;for(int i = 1; i < nums.length(); i++){ if(nums[i] == '0')if(nums[i - 1] != '1' && nums[i - 1] != '2')return 0;}for(int i=2;i<nums.size();i++){if((nums[i-1]=='1'&&nums[i]!='0')||(nums[i-1]=='2'&&nums[i]<='6'&&nums[i]>'0')){ans[i]=ans[i-2]+ans[i-1];}else ans[i]=ans[i-1];}return ans[nums.size()-1];}
};

正则表达式匹配_牛客题霸_牛客网 (nowcoder.com)

又是蛇皮烦的一题……

首先，还是设置dp数组，dpij代表str第i位结尾、pattern第j位结尾的子字符串能否匹配。假设第i-1

位和第j-1位能成功匹配，那么此时就是要对比第i位和第j位字符关系，如果两个都是小写字母，且相同，那么dpij的结果就是dpi-1j-1的结果。如果不符合可以直接判断为false。

因此第j位如果是.代表着任意字符，所以转移公式可以等同于上面的情况。

接下来就是考虑第j位为*的情况，此时要把第j-1位一同考虑，当作整体，下面将j-1视作a。

第一种情况是假定*为0次，此时dpij的结果就和dpij-2的结果相同。

第二种情况是假定*为1次，因为如果前面*已经被当成a的话此时已经成功匹配了，可以忽略了，后面同理。假定为一次的话j-1就要等同于i，*才能变成第i位进行匹配，那么此时的转移公式就是dpij=dpi-1j

第一种情况和第二种情况可以同时存在，符合条件的时候取或就行。

#include <vector>
class Solution {bool match(string str, string pattern) {vector<vector<int> >dp;vector<int> temp(30, 0);dp.resize(30, temp);dp[0][0] = 1;for (int i = 1; i <= pattern.size(); i++) {if (pattern[i]=='*')dp[0][i+1]=dp[0][i-1];}for (int i = 0; i < str.size(); i++) {for (int j = 0; j < pattern.size(); j++) {if (str[i] == pattern[j] || pattern[j] == '.') {dp[i + 1][j + 1] = dp[i][j];} else {if (pattern[j] == '*') {dp[i+1][j+1]=dp[i+1][j-1];if(pattern[j-1]=='.'||pattern[j-1]==str[i]){dp[i+1][j+1]=dp[i][j+1]||dp[i+1][j+1];}}}}}if (dp[str.size()][pattern.size()] == 1)return true;else return false;}
};