# 常见动态规划题目详解

1.爬楼梯

1. 1 阶 + 1 阶
2. 2 阶

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

class Solution {
public:
int climbStairs(int n) {
vector<int> a(n);
a[0] = 1;
a[1] = 2;
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
for(int i = 2; i < n;i++){
a[i] = a[i - 1] + a[i - 2];
}
return a[n - 1];
}
};

2.变态跳台阶

class Solution {

public:
int jumpFloorII(int number) {
if(number == 0){
return 0;
}
int total = 1;
for(int i = 1; i < number; i++){
total *= 2;
}
}
};
3.n年后牛的数量

class solution{
public:
int f(int n){
if(n < 1){
return 0;
}
if(n == 1|| n== 2||n == 3){
return n;
}
int res = 3;
int pre = 2;
int prepre = 1;
int tmp1=0;
int tmp2 = 0;
for(int i = 4;i < n;i++){
tmp1 = res;
tmp2 = pre;
res = pre + prepre;
pre = tmp1;
prepre = tmp2;
}
return res;
}

} ;
4.矩形覆盖

class Solution {
public:
int rectCover(int number) {
if(number <= 2){
return number;
}
int first = 1, second = 2, third = 0;
for(int i = 3; i <= number; i++){
third = first + second;
first = second;
second = third;
}
return third;
}
};
5.最小路径和

[
[1,3,1],
[1,5,1],
[4,2,1]
]

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

6.机器人到达指定位置的方法数

N个位置，1~N,N大于等于2，开始时机器人在其中的M位置，它可以向左或者右走。如果到了位置1，下一步只能是位置2；如果到了位置N,下一步只能是位置 N-1 。机器人走 K 步，最终来到位置 P 的总方法一共有多少种？

(1).暴力递归

class Solution {
public:
int ways(int N,int M,int K,int P){
if(N < 2 || K < 1|| M < 1|| M > N||P < 1||P > N){
return 0;
}
return walk(N,M,K,N);
}
int walk(int N,int cur,int rest,int P){
if(rest == 0){
return cur == p ? 1 : 0;
}
if(cur == 1){
return walk(N,2,rest - 1,P);
}
if(cur == N){
return walk(N,N - 1,rest - 1,P);
}
return walk(N,cur + 1,rest - 1,P) + walk(N,cur - 1,rest - 1,P);
}
};

(2)动态规划：

class Solution {
public:
int way(int N,int M,int K,int P){
if(N < 2|| K < 1||M < 1||M > N||P < 1|| P > N){
return 0;
}
vector<vector<int>>dp(K + 1,(vector<int>(N + 1)));
dp[0][p] = 1;
for(int i = 1;i <= K;i++){
for(int int j = 1;j < N;j++){
if(j == 1){
dp[i][j] = dp[i - 1][2];
}
else if(j == N){
dp[i][j] = dp[i - 1][N - 1];
}
else{
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
}
}
}
return dp[K][M];
}
};

7.不同路径

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

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

8.不同路径Ⅱ

[
[0,0,0],
[0,1,0],
[0,0,0]
]

3x3 网格的正中间有一个障碍物。

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(); //行数
int n = obstacleGrid[0].size();//列数
long p[m][n];

//第一列赋值
int k = 0;
while(k < m && obstacleGrid[k][0] != 1)
p[k++][0] = 1;
//如果遇到了障碍物则它及其后面的值都为0
while(k < m)
p[k++][0] = 0;

//第一行赋值
k = 0;
while(k < n && obstacleGrid[0][k] != 1)
p[0][k++] = 1;
while(k < n)
p[0][k++] = 0;

for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 1) //如果遇到障碍物，则该位置的值为0
p[i][j] = 0;
else
p[i][j] = p[i - 1][j] + p[i][j - 1];
}
return p[m-1][n-1];
}
};

9.买卖股票的最佳时机

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

};

10.打家劫舍

偷窃到的最高金额 = 1 + 3 = 4 。

偷窃到的最高金额 = 2 + 9 + 1 = 12 。

(1).递归+记忆化搜索

class Solution {
public:
vector<int>tmpt;
int tryrob(vector<int>& nums,int index){
if(index >= nums.size()){
return 0;
}
if(tmpt[index] != -1){
return tmpt[index];
}
int tmp = -1;
for(int i = index;i < nums.size();i++){
tmp = max(tmp,nums[i] + tryrob(nums,i + 2));
}
tmpt[index] = tmp;
return tmp;
}
int rob(vector<int>& nums) {
tmpt = vector<int>(nums.size(),-1);
return tryrob(nums,0);
}

}；

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

11.整数拆分

class Solution {
private:
vector<int>tmpt;
int res(int n){
if(n == 1){
return 1;
}
if(tmpt[n] != -1){
return tmpt[n];
}
int tmp = -1;
for(int i = 1;i < n;i++){
tmp = max(max(tmp,i * (n - i)),i * res(n - i));
}
tmpt[n] = tmp;
return tmp;
}

public:
int integerBreak(int n) {
tmpt = vector<int>(n + 1,-1);
return res(n);
}

}；

class Solution {

public:
int integerBreak(int n) {
vector<int>tmp(n+1,-1);
tmp[1] = 1;
for(int i = 2;i <= n;i++){
for(int j = 1;j < i;j++){
tmp[i] = max(max(tmp[i],j * (i - j)),j * tmp[i - j]);
}
}
return tmp[n];
}
};

12.三角形最小路径和

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

(1).递归+记忆化搜索

class Solution {
public:
vector<vector<int>> tmp;
int min_value(vector<vector<int>>& triangle,int i,int j){
if(i == triangle.size() - 1){
return triangle[i][j];
}
if(tmp[i][j] == -1)
tmp[i][j] = triangle[i][j] + min(min_value(triangle,i + 1,j),min_value(triangle,i + 1,j + 1));
return tmp[i][j];
}

int minimumTotal(vector<vector<int>>& triangle) {
int res = 0;
tmp = vector<vector<int>> (1000,vector<int>(1000,-1));
res = min_value(triangle,0,0);
return res;

}

};

(2).动态规划

class Solution {

public:

int minimumTotal(vector<vector<int>>& triangle) {

if(triangle.size() == 0){

return 0;

}

vector<int>res;

int tmp = 0;

for(int i = triangle.size() - 2;i >= 0;i--){

for(int j = 0;j < triangle[i].size();j++){

triangle[i][j] = min(triangle[i + 1][j],triangle[i + 1][j + 1]) + triangle[i][j];

}

}

return triangle[0][0];

}

};

13.最长回文子串

(1).暴力

class Solution {

public:

string longestPalindrome(string s)

{

if(s.empty()) return "";

if(s.size()==1) return s;

int start=0,maxlength=1;//记录最大回文子串的起始位置以及长度

for(int i=0;i<s.size();i++)

for(int j=i+1;j<s.size();j++)//从当前位置的下一个开始算

{

int temp1,temp2;

for(temp1=i,temp2=j;temp1<temp2;temp1++,temp2--)

{

if(s[temp1]!=s[temp2])

break;

}

if(temp1>=temp2 && j-i+1>maxlength)//这里要注意条件为temp1>=temp2，因为如果是偶数个字符，相邻的两个经上一步会出现大于的情况

{

maxlength = j-i+1;

start=i;

}

}

return s.substr(start,maxlength);//利用string中的substr函数来返回相应的子串,第一个参数是起始位置，第二个参数是字符个数*/

}

}；

(2).动态规划

class Solution {

public:

string longestPalindrome(string s)

{

if (s.empty()) return "";

int len = s.size();

if (len == 1)return s;

int longest = 1;

int start=0;

vector<vector<int> > dp(len,vector<int>(len));

for (int i = 0; i < len; i++)

{

dp[i][i] = 1;

if(i<len-1)

{

if (s[i] == s[i + 1])

{

dp[i][i + 1] = 1;

start=i;

longest=2;

}

}

}

for (int l = 3; l <= len; l++)//子串长度

{

for (int i = 0; i+l-1 < len; i++)//枚举子串的起始点

{

int j=l+i-1;//终点

if (s[i] == s[j] && dp[i+1][j-1]==1)

{

dp[i][j] = 1;

start=i;

longest = l;

}

}

}

return s.substr(start,longest);

}

};

14.最大字序和

class Solution {

public:

int maxSubArray(vector<int>& nums) {

int sum = 0;

int max_sum = nums[0];

for(int i = 0;i < nums.size();i++){

if(sum <= 0){

sum = nums[i];

}

else

sum = sum + nums[i];

if(max_sum < sum){

max_sum = sum;

}

}

return max_sum;

}

};

15.最长上升子序列

class Solution {

private:

int dp[100000];

int LIS(vector<int> &nums,int n){

if(n == 0){

dp[n] = 1;

return dp[n];

}

for(int i = n;i>= 0;i--){

for(int j = i - 1;j >= 0;j--){

if(nums[i] <= nums[j]){

dp[n] = max(LIS(nums,n - 1),;

}

if(nums[n] > nums[n - 1]){

dp[n] = LIS(nums,n-1);

}

}

}

return dp[n];

}

public:

int lengthOfLIS(vector<int>& nums) {

if(nums.size() == 0){

return NULL;

}

int n = nums.size() - 1;

return LIS(nums,n);

}

};

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if(nums.size() == 0){

return NULL;

}

int *dp = new int[nums.size()];

int len = nums.size();

int res = 0;

for(int i = 0;i < len;i++){

dp[i] = 1;

for(int j = 0;j < i;j++){

if(nums[i] > nums[j]){

dp[i] = max(dp[j] + 1,dp[i]);

}

}

res = max(dp[i],res);

}

return res;

}

};

16.最长公共子序列

class Solution {

public:

int maxlength(string str1,string str2){

int m = str1.length();

int n = str2.length();

vector<vector<int>>dp(m,vector<int>(n));

dp[0][0] = str1[0] == str2[0]?1:0;

for(int i = 0;i < m;i++){

dp[i][0] = max(dp[i - 1][0],str1[i] == str2[0]?1:0);

}

for(int j = 0;j < n;j++){

dp[0][j] = max(dp[0][j - 1],str1[0] == str[j] ? 1: 0);

}

for(int i = 1; i < m;i++){

for(int j = 1;j < n;j++){

dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);

if(str1[i] == str2[j]){

dp[i][j] = max(dp[i][j],1 + dp[i - 1][j - 1]);

}

}

}

return dp[m - 1][n - 1];

}

};

17.最长公共字串

class Solution {

public:

int maxlength(string str1,string str2){

int m = str1.length();

int n = str2.length();

vector<vector<int>>dp(m,vector<int>(n));

for(int i = 0;i < m;i++){

if(str1[i] == str2[0]){

dp[i][0] = 1;

}

}

for(int j = 0;j < n;j++){

if(str2[j] == str1[0]){

dp[0][j] = 1;

}

}

for(int i = 1;i < m;i++){

for(int j = 1;j < n;j++){

if(str1[i] == str2[j]){

dp[i][j] = dp[i - 1][j - 1] + 1;

}

}

}

return dp[m - 1][n - 1];

}

};

18.连续子数组和

class Solution {

public:

bool checkSubarraySum(vector<int>& nums, int k) {

int m = nums.size();

if(m < 2){

return false;

}

int sum[m];

sum[0] = nums[0];

for(int i = 1;i < m;i++){

sum[i] = sum[i - 1] + nums[i];

}

for(int i = 0;i < m;i++){

for(int j = i + 1;j < m;j++){

int res = sum[j] - sum[i] + nums[i];

if(res == k || (k != 0 && res % k == 0)){

return true;

}

}

}

return false;

}

};