动态规划刷题总结

关于动态规划的步骤:

1.dp数组的以及下标的含义
2.递推公式
3.dp数组如何初始化
4.遍历顺序
5.打印dp数组。

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

解题思路

使用动态规划的方法，首先，创建一个dp数组，初始值为1，长度为nums的长度。这里将每个数组元素的初始值设为1，是当一个子序列中只有一个元素时，也就是这个元素本身，所以长度设为1。

然后我们分别设置2个指针进行遍历这个数组，设置left、right，让right指针从第0个元素进行遍历这个数组，让left也从第0个元素进行遍历元素且left<right,当left等于right时，让left=0从第0个元素进行遍历，right++.

当nums[left]<nums[right]时，我们比较dp[left]+1和dp[right]的大小，若dp[left]+1>dp[right],我们就让dp[right]=dp[left]+1,否则，就让dp[right]=dp[right]。

最后我们返回dp数组的最大值即可。

时间复杂度：O(n的平方)，n为nums的长度，动态规划的状态数为n,所以时间复杂度为O(n的平方)。

空间复杂度：O(n),n为使用的dp数组的长度。

代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        if(n==0)
        return 0;
        int maxes=1;
        vector<int> dp(n,1);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        maxes=max(maxes,dp[i]);
        }

return maxes;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

70. 爬楼梯

设置dp数组，用于保存从第一层到第n层的种数。则dp[n]=dp[n-1]+dp[n-2]，从第三层开始，初始化dp[1]=1,dp[2]=2.

class Solution {
public:
    int climbStairs(int n) {
if(n<=1)
return n;
vector<int> dp(n+1);
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++)
{
    dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

746. 使用最小花费爬楼梯

创建dp数组，用于保存从第0层或第1层到第n层所需要的花费。dp[i]=min(dp[i-1],dp[i-2])+cost[i],为第i层的花费为第i-1层与第i-2层的最小值加上第i层的花费。到达最后一层时，认为不用花费精力，所以最后返回的是第n-1层或n-2层的最小值。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size());
dp[0]=cost[0];
dp[1]=cost[1];
for(int i=2;i<cost.size();i++)
dp[i]=min(dp[i-1],dp[i-2])+cost[i];
return min(dp[cost.size()-1],dp[cost.size()-2]);


    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

62. 不同路径

思路：

1.dp数组的含义：
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
2.递推公式：
想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。
3.dp数组的初始化
如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
4.确定遍历顺序
这里要看一下递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
时间复杂度：O(mn)。

空间复杂度：O(mn)，

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++)
        dp[i][0]=1;
        for(int j=0;j<n;j++)
        dp[0][j]=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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

63. 不同路径 II

解题思路：
1.初始化dp数组
当增加了障碍物后，在初始化数组时，我们对dp[i][0],dp[0][j]元素初始化为1时，因为有障碍物，我们对障碍物前的元素初始化为1，对障碍物后的元素不进行初始化。
2.递推公式
当obstacleGrid[i][j]为1时，我们停止对dp[i][j]的点进行递推遍历。
3.确定遍历顺序
这里要看一下递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

代码：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m&&obstacleGrid[i][0]==0;i++)
        dp[i][0]=1;
        for(int j=0;j<n&&obstacleGrid[0][j]==0;j++)
        dp[0][j]=1;
         for(int i=1;i<m;i++)
    for(int j=1;j<n;j++){
        if(obstacleGrid[i][j]==1)
        continue;
        dp[i][j]= dp[i-1][j] +dp[i][j-1];

    }
     return dp[m-1][n-1];    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

343. 整数拆分

确定dp数组（dp table）以及下标的含义
1

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

dp[i]的定义讲贯彻整个解题过程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！

确定递推公式
可以想 dp[i]最大乘积是怎么得到的呢？

其实可以从1遍历j，然后有两种渠道得到dp[i].

一个是j * (i - j) 直接相乘。

一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。
这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，

确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

枚举j的时候，是从1开始的。i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。

class Solution {
public:
    int integerBreak(int n) {
vector<int> dp(n+1);
dp[2]=1;
for(int i=3;i<=n;i++)
for(int j=1;j<i-1;j++)
dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));
return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11

416. 分割等和子集

思路：
这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

确定dp数组以及下标的含义
01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值可以最大为dp[j]。

套到本题，dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]。

确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

dp数组如何初始化
在01背包，一维dp如何初始化，已经讲过，

从dp[j]的定义来看，首先dp[0]一定是0。

如果如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
int sums=0;
for(int i=0;i<nums.size();i++)
{
    sums+=nums[i];
}
int target=sums/2;

if(sums%2==1)
return false;

vector<int> dp(10001,0);

for(int i=0;i<nums.size();i++)
for(int j=target;j>=nums[i];j--)
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);

if(dp[target]==target)
return true;
else
return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25