柚子快报邀请码778899分享：算法 动态规划
动态规划解题五部曲
确定dp数组（dp table）以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
01背包
不同路径
. - 力扣（LeetCode）
题目描述：给定一个m x n 的网格，一机器人的起点在左上角，终点在右下角。机器人每次只能向下和向右走。问从起点到终点有多少种不同路径。
解题思路：确定一个dp数组。
1、dp[i][j]：表示从起点到i,j位置有多少种不同路径。 2、递推公式：机器人每次只能向下和向右走，所以dp[i][j] = dp[i-1][j] + dp[i][j-1]。当确定位置i,j时，需要向该位置的上方和左方去确定。dp[i-1][j]表示i,j位置的上方位置有多少种路径；dp[i][j-1]表示i,j位置的左方位置有多少种路径。 3、dp数组初始化：由递推公式dp[i][j] = dp[i-1][j] + dp[i][j-1]可知，每一个位置的值是由该位置的上方和左方确定的。所以需要初始化dp数组的第一行和第一列。当机器人一直向右走，可得第一行的dp数组的值为1；当机器人一直向下走，可得第一列得dp数组的值为1。 4、遍历顺序：自然是遍历除了第一行和第一列的整个数组了。
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[101][101];
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];
}
};
优化
dp数组也可以使用一维数组。每一次在dp数组上赋值，dp[i-1][j] = dp[j]; dp[i][j-1] = dp[j-1]
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[101];
for(int i = 0; i < n; i++)
dp[i] = 1;
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
dp[j] = dp[j-1] + dp[j];
}
return dp[n-1];
}
};
不同路径II
. - 力扣（LeetCode）
题目描述：相对于上一题来说，在网格中添加了障碍，障碍会挡住机器人。
解题思路：思路和上一题差不多，就是多了对于障碍的处理。当网格中有障碍的位置，机器人是到达不了该位置的。对遍历的处理逻辑和dp数组的初始化会有改变
遍历的处理
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
if(obstacleGrid[i][j] == 1) // 当该位置有障碍的时候
dp[i][j] = 0;
else
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
dp数组初始化
int n = obstacleGrid.size(), m = obstacleGrid[0].size();
vector
// 先给dp数组整体赋值为0
for(int i = 0; i < n && obstacleGrid[i][0] == 0; i++) // 当遇到障碍，后面的全部都是0
dp[i][0] = 1;
for(int i = 0; i < m && obstacleGrid[0][i] == 0; i++)
dp[0][i] = 1;
// 当不给dp数组初始化为0时，也可以这样赋值
for(int i = 0; i < n; i++)
{
if(obstacleGrid[i][0] == 1)
dp[i][0] = 0;
else
{
if(i > 0 && dp[i-1][0] == 0)
dp[i][0] = 0;
else
dp[i][0] = 1;
}
}
for(int i = 0; i < m; i++)
{
if(obstacleGrid[0][i] == 1)
dp[0][i] = 0;
else
{
if(i > 0 && dp[0][i-1] == 0)
dp[0][i] = 0;
else
dp[0][i] = 1;
}
}
整体代码
class Solution {
public:
int uniquePathsWithObstacles(vector
int n = obstacleGrid.size(), m = obstacleGrid[0].size();
vector
for(int i = 0; i < n && obstacleGrid[i][0] == 0; i++)
dp[i][0] = 1;
for(int i = 0; i < m && obstacleGrid[0][i] == 0; i++)
dp[0][i] = 1;
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
if(obstacleGrid[i][j] == 1)
dp[i][j] = 0;
else
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[n-1][m-1];
}
};
优化
同样也可以使用滚动数组，使用一维的dp数组
class Solution {
public:
int uniquePathsWithObstacles(vector
int n = obstacleGrid.size(), m = obstacleGrid[0].size();
vector
for(int i = 0; i < m && obstacleGrid[0][i] == 0; i++)
dp[i] = 1;
for(int i = 1; i < n; i++)
{
for(int j = 0; j < m; j++) // 注意这里是从j = 0 开始的
{
if(obstacleGrid[i][j] == 1)
dp[j] = 0;
else if(j > 0)
dp[j]= dp[j-1] + dp[j];
// 当j = 0时，并且没有障碍，那么就和上一行的dp[0]是一样的值，不需要修改
}
}
return dp[m-1];
}
};
整数拆分
. - 力扣（LeetCode）
题目描述：给定一个整数n，要求将整数拆分为k个数的和，求拆分k个数的最大乘积。
解题思路：确定dp数组的含义：dp[i]：表示将i拆分求得的最大乘积dp[i]。
递推公式：对于i，可以分为两种情况拆分：拆分为两项或多项。两项：i * (i - j)；多项：i * dp(i - j) 那为什么要这样拆分呢？举个例子：对于n = 3这种情况。拆分为两项是：2 * 1 = 2；拆分为多项式：1 * 1 * 1 = 1。明显拆分为两项是大于拆分为多项的。那为什么拆分多项是：j * dp[i-j]？这需要再联系dp数组的含义。dp[i-j]是将i - j拆分k项所得的最大乘积。那么由此可得递推公式为：dp[i] = max(j * (i - j), j * dp[i-j])
初始化：dp[0]、dp[1] 都为0，没有意义。从dp[2]开始才有意义，dp[2] = 1。
class Solution {
public:
int integerBreak(int n) {
vector
dp[2] = 1;
for(int i = 3; i <= n; i++)
{
for(int j = 1; j <= i / 2; j++)
// j <= i / 2是一个优化。由数学推导可得：将一个数拆分只有拆得数越相等，得到的乘积才最大
dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j)));
}
return dp[n];
}
};
贪心
本题还可以使用贪心，对于一个大于3的整数，只有尽可能的拆分成3相乘，最后剩余的整数为4，这样得到的乘积才最大。证明方法需要用到函数极值证明，或数学归纳法
class Solution {
public:
int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
if (n == 4) return 4;
int result = 1;
while (n > 4) {
result *= 3;
n -= 3;
}
result *= n;
return result;
}
};
不同的二叉搜索树
. - 力扣（LeetCode）
题目描述：给定一个结点树n，问由n个结点组成的不同的二叉搜索树有多少颗。
二叉搜索树的性质是根结点大于左子树结点，右子树结点大于根节点。
当求结点数为n时，需要选1 ~ n 作为根结点，那么选该结点作为根节点时，组成的不同二叉树种数有：左子树组成种类 * 右子树组成种类。 根据上图可知：当n = 3时，我们是通过头节点为1，2，3，然后在计算它们的左右子树，左右子树所组成的种类可以通过前面已经推导的种类所计算出来。 所以当n = 3时可组成的二叉搜索树的种类 = 1为头结点组成的种类 + 2为头结点组成的种类 + 3为头结点组成的种类。那么对于任意n，求组成的二叉搜索树的种类，需要以[1,n]为头节点，根据二叉搜索树的性质可得：头结点的左子树都比头结点小，右子树都比头节点大。
确定dp数组的含义：dp[i]表示由i个结点可以组成dp[i]种不同的二叉搜索树。
递推公式：以j遍历[1,i]，用j作为组成的二叉搜索树头节点，那么左子树的结点树有j - 1个，右子树有i - j个。这是通过二叉搜索树的性质得到的。那么递推公式为：dp[i] += dp[j-1] + dp[i-j]。
class Solution {
public:
int numTrees(int n) {
vector
dp[0] = 1; // 一颗空树也是一颗二叉搜索树
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
dp[i] += dp[j-1] * dp[i-j]; // 注意这里+=
}
return dp[n];
}
};
打家劫舍
题目链接：. - 力扣（LeetCode）
题目分析：题目要求相邻的两家不能偷窃，需要计算可以偷的最大金额。 确定dp数组的含义：dp[i]表示在[1,i]房间能偷的最大金额。 递推公式：题目要求不能偷相邻的两家，那么dp[i] = max(dp[i-1], dp[i-2] + nums[i])。dp[i-1]：表示不偷第i家；dp[i-2] + nums[i]：表示偷了第i家。 初始化：由递推公式可知，dp[i]是由第i家之前两家的情况而确定的，所以dp[0] = nums[0]; dp[1] = max(dp[0], nums[1])。当然还得判断一下是否只有一家。
class Solution {
public:
int rob(vector
int n = nums.size();
if(n == 1)
{
return nums[0];
}
int dp[101];
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < n; i++)
{
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
// 选i这个位置前一个位置的值，不选前一个的值，那么就符合没有相邻的情况，就可以加上nums[i]
}
return dp[n - 1];
}
};
空间优化
class Solution {
public:
int rob(vector
if(nums.size() == 1) return nums[0];
// 优化空间
int res1 = nums[0];
int res2 = max(nums[1], res1);
for(int i = 2; i < nums.size(); i++)
{
int temp = res2;
res2 = max(res2, res1 + nums[i]);
res1 = temp;
}
return res2;
}
};
删除并获得点数
题目链接：. - 力扣（LeetCode）
解题思路：当选择一个元素x，那么x-1和x+1都应该被删除，则应该选择全部的x，这样点数才会最大。我们可以用一个哈希表把数组中所有元素x的和存储在下标x中，那么x-1和x+1的下标不能选择，那么就可以抽象成一个打家劫舍问题了。
class Solution {
public:
int rob(vector
if(nums.size() == 1) return nums[0];
// 优化空间
int res1 = nums[0];
int res2 = max(nums[1], res1);
int res = res2;
for(int i = 2; i < nums.size(); i++)
{
res = max(res2, res1 + nums[i]);
res1 = res2;
res2 = res;
}
return res;
}
int deleteAndEarn(vector
int n = nums.size();
vector
for(int i = 0; i < n; i++)
{
sum[nums[i]] += nums[i];
}
return rob(sum);
}
};
买卖股票的最佳时机
题目链接：. - 力扣（LeetCode）
解题思路：本题暴力很容易想到，但是会超时。我们不如把思路逆转过来，不去找哪一天买入，而是以卖出的日子作为基点考虑，遍历一遍数组，以每一天作为卖出出来计算最大值即可。那么买入肯定是要在卖出前的最小值。
class Solution {
public:
int maxProfit(vector
int min_price = prices[0];
int res = 0;
for(int price : prices)
{
res = max(res, price - min_price);
min_price = min(min_price, price);
}
return res;
}
};
分割等和子集
题目链接：. - 力扣（LeetCode）
解题思路：题目要求就是能否在数组中找到一个子集和等于整个数组和的一半。可以使用01背包解决。 dp数组：表示在容量为i的背包中有dp[i]的价值。这个容量就是整个数组和的一半，设为v，最后有dp[v] = v. 递推公式：dp[i] = max(dp[i], dp[i - nums[i]] + nums[i])。这个递推公式已经很熟悉了。就当第i个元素不选时为：dp[i]。当选时为：dp[i - nums[i]] + nums[i] 初始化：显然dp[0] = 0；根据递推公式，dp数组应该初始化为0，因为对于任意dp[i]都是由前面的dp数组的值得到的最大值，自然前面的dp数组的值不能影响到dp[i]的值，所以初始化为0.
class Solution {
public:
bool canPartition(vector
int n = nums.size();
int sum = 0;
for(int e : nums)
sum += e;
if(sum % 2 != 0) return false; // 当容量为奇数时
int v = sum / 2;
vector
for(int i = 0; i < n; i++)
{
for(int j = v; j >= nums[i]; j--) // 注意这里是倒序，对于一个容量必须要大于 考虑放入的物品的体积。不然就不用放。
dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
}
return dp[v] == v;
}
};
最后一块石头的重量II
题目链接：. - 力扣（LeetCode）
解题思路：这题很难想到用01背包求解，题目要求最后一块石头的最小重量。当两块重量最相似的石头相撞可以得到最小重量。那么将这堆石头分成两堆重量和相似。设总和为sum，那么一堆为sum/2，另外一堆就是sum - sum/2。那么题目就可转换为在这一堆石头中找可以构成重量为sum/2的重量。那么最后结果就(sum/2 - (sum - sum/2))。那么接下来思路和上一题差不多
class Solution {
public:
int lastStoneWeightII(vector
vector
int n = stones.size();
int sum = 0;
for (int i = 0; i < n; i++)
sum += stones[i];
int target = sum / 2;
for(int i = 0; i <= target; i++)
{
if(i >= stones[0])
dp[i] = stones[0];
}
for (int i = 1; i < n; i++)
{
for (int j = target; j >= stones[i]; j--)
{
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};
目标和
题目链接：. - 力扣（LeetCode）
解题思路：题目要求计算组成target的组合。通过‘+'或‘-’运算。那么可以把数组的元素分成加法集合a和减法集合b，那么可得a - b = target；设数组的和为sum；那么a + b = sum；b = sum - a；那么a - (sum - a) = target；a = (sum + target) / 2。sum 和 target都是确定的，就可以得到a。题目就可转换为在数组中求可以构成a的组合。已知数组都是正整数组成的，所以a肯定不能为小数，所以当2不能整除sum - target时，不能组成target。target是由数组中的元素组成的，那么target不能超过数组的和的范围，也就是 target∈[-sum, sum]。当target超出这个范围，那么也不能构成target。 至此题目就转换为：在数组中求可以构成a的组合。那么可以使用01背包来求解，a就是背包的最大容量，数组的元素就是价值，求用价值组成容量的方法。 dp数组的含义：dp[j]表示能装满容量为j的背包，有dp[j]种方法。递推公式：对于一个容量来说，求解能组成它的方法，可以根据已经有的元素，去找能构成减去该元素的容量的方法。换句话说，就是求dp[j]，那么对于求j容量的组成方法，可以先确定一个元素（设该元素为x)，这个元素可以抽象为物品的价值，我们将这个背包的容量缩小x，那么就是dp[j-x] 然后元素x，就数组中的每一个元素。而dp[j]的前面元素都是根据前面的前面dp数组求出来的。所以累加dp数组，就可以得到一个容量的组成方法数了。举个例子：当a = 5时；求能构成容量为5的组合数。当确定一个元素1，那么它就可以由dp[4]构成；当确定元素2，那么就由dp[3]构成；当确定元素3，那么就由dp[2]构成；当确定元素4，那么就由dp[1]构成；…………最后，当数组中的元素遍历完了，最后dp[5]就等于dp[4]、dp[3]、dp[2]、dp[1]、dp[0]之和。所以递推公式为：dp[j] += dp[j - nums[i]]
初始化：根据递推公式，需要初始化dp[0]，那么dp[0]到底为1还是0，当dp[0] = 0，那么后面的dp数组都为0了，所以dp[0] = 1。而0后面的dp数组可以根据dp[0]推导出来，所有0之后的dp数组初始化为0。
class Solution {
public:
int findTargetSumWays(vector
int n = nums.size();
int sum = 0;
for(int e : nums)
sum += e;
if((sum + target) % 2 == 1)
return 0;
if(abs(target) > sum)
return 0;
int v = (sum + target) / 2;
vector
dp[0] = 1;
for(int i = 0; i < n; i++)
{
for(int j = v; j >= nums[i]; j--)
{
dp[j] += dp[j-nums[i]];
}
}
return dp[v];
}
};
一和零
题目链接：. - 力扣（LeetCode）
解题思路：题目要求给定一个字符串数组，需要选用字符串组成m个0和n个1，问最多的组成子集。那么可以选用一个背包，两个容量维度；一个容量是m，一个容量是n。dp数组的含义：dp[i][j]表示装i个0和j个1最多有dp[i][j]个子集。递推公式：对于每个字符串，也就是背包中的物品，可以选择装和不装，先计算出物品中0的个数x，和1的个数y；当不装该物品子集个数是：dp[i][j]；当装该物品子集个数是：dp[i-x][j-y] + 1。然后求最大值即可。那么递推公式为：dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1) 遍历顺序：先遍历物品，再遍历容量。容量需要倒序遍历
class Solution {
public:
int findMaxForm(vector
vector
for(string e : strs)
{
int x = 0, y = 0;
for(char ch : e)
{
if(ch == '0')
x++;
else
y++;
}
for(int i = m; i >= x; i--)
{
for(int j = n; j >= y; j--)
dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1);
}
}
return dp[m][n];
}
};
完全背包
完全背包是对于一个物品可以多次使用，01背包是每个物品只能使用一次。所以完全背包在遍历容量采用正序遍历
零钱兑换II
题目链接：. - 力扣（LeetCode）
解题思路：该题求得也是方法数，和前面的目标和很像。这种题目可以抽象为：给定一个容量，去选择物品去装满背包，问有多少种选法。只不过在前面目标和题目中，每种物品只能使用一次，而该题可以多次使用同一种物品。两个题目也就在遍历背包容量时顺序不同。其他都是一样的。
注意：该题先遍历物品再遍历背包，不可颠倒。因为求的是组合数。而先遍历背包再遍历物品求的是排列。 先遍历物品再遍历背包：是在物品中按照顺序依次取出一个物品，那么后面取出的物品肯定不是前面的物品。先遍历背包再遍历物品：对于背包的容量依次去考虑放入物品（需要从容量等于0开始）。每次考虑一个容量，然后再依次拿出物品，而对于每个背包容量可以组成的方法数，都是由前面的容量可以组成的方法数得到的。那么前面背包容量可以组成的方法数，可能已经包含了即将要取出的物品。举个例子：当coins=[1,2,5]；amount = 5。那么对于dp[0] = 1； 考虑dp[1]：只能放入元素1， 所以dp[1] = 1. 【1】 考虑dp[2]：可以放入元素1，这个时候需要加上背包容量为1时的方法数（dp[1]）；也可以放入元素2，这个时候需要加上背包容量为0时的方法数（dp[0]）。即dp[2] = 2。【1，1】；【2】 考虑dp[3]：可以放入元素1，这个时候需要加上背包容量为2时的方法数（dp[2]）；也可以放入元素2，这个时候需要加上背包容量为1的方法数（dp[1]）。即dp[3] = 3。【1，1，1】；【1，2】；【2，1】。这是排列数，并不是组合。
class Solution {
public:
int change(int amount, vector
vector
dp[0] = 1;
for(int i = 0; i < coins.size(); i++)
{
for(int j = coins[i]; j <= amount; j++)
{
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
};
柚子快报邀请码778899分享：算法 动态规划
文章来源
发表评论