当前位置：网站首页>动态规划、背包问题 6/24 106-110
动态规划、背包问题 6/24 106-110
2022-08-10 05:36:00 【吉良吉影__.】
1.买卖股票的最佳时机含手续费(LeetCode 714)
动态规划
此题同
买卖股票的最佳时机II（ LeetCode 122 ）
思想相似
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices.length < 1)return 0;
int buy = -prices[0];//第i天结束手中持有股票的最大利润
int sell = 0;//第i天结束手中未持有股票的最大利润
for (int i = 1; i < prices.length; i++) {
int preBuy = buy;
buy = Math.max(buy,sell - prices[i]);
sell = Math.max(sell,preBuy + prices[i] - fee);
}
return sell;
}
}
2.完全平方数（ LeetCode 279 ）
解法一：
完全背包朴素数组
class Solution {
public int numSquares(int n) {
if (n < 2)return n;
List<Integer> list = new ArrayList<>();
//寻找小于n的所有完全平方数
for (int i = 1; i * i <= n; i++) list.add(i * i);
//dp[i][j] 前i个数中进行寻找，凑成j的最小数量
int[][] dp = new int[list.size()][n + 1];
//初始化
for (int i = 0; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 1; i < list.size(); i++) {
for (int j = 0; j <= n; j++) {
//不选第i个元素
int no = dp[i - 1][j];
//选第i个元素
int yes = Integer.MAX_VALUE;
//第i个元素可选0 ~ k次
for (int k = 1; ; k++) {
if (k * list.get(i) > j)break;
yes = Math.min(yes,dp[i - 1][j - k * list.get(i)] + k);
}
dp[i][j] = Math.min(no,yes);
}
}
return dp[list.size() - 1][n];
}
}
解法二：
完全背包一维数组优化
class Solution {
public int numSquares(int n) {
if (n < 2)return n;
List<Integer> list = new ArrayList<>();
for (int i = 1; i * i <= n; i++) list.add(i * i);
int[] dp = new int[n + 1];
//初始化
for (int i = 0; i <= n; i++) {
dp[i] = i;
}
for (int i = 1; i < list.size(); i++) {
int num = list.get(i);
for (int j = 0; j <= n; j++) {
//不选当前元素
int no = dp[j];
//选当前元素
int yes = j >= num ? dp[j - num] + 1 : Integer.MAX_VALUE;
dp[j] = Math.min(no,yes);
}
}
return dp[n];
}
}
解法三：官方解 动态规划
class Solution {
public int numSquares(int n) {
/* dp[i] : 构成数字i所需最少的平方数 dp[i] = 1 + Ma.min( dp[i - j * j] ) ,其中 0 < j <= 根号i */
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
min = Math.min(min,dp[i - j * j]);
}
dp[i] = min + 1;
}
return dp[n];
}
}
3.三角形最小路径和（ LeetCode 120 ）
动态规划
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
//f[i][j] 到达第i行j列的最短距离
int[][] f = new int[n][n];
f[0][0] = triangle.get(0).get(0);
for (int i = 1; i < n; ++i) {
//每行的第一个元素与最后一个元素特殊对待
f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
for (int j = 1; j < i; ++j) {
//状态转移方程
f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
}
f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
}
//寻找最后一行的最小值
int minTotal = f[n - 1][0];
for (int i = 1; i < n; ++i) {
minTotal = Math.min(minTotal, f[n - 1][i]);
}
return minTotal;
}
}
4.不同路径（ LeetCode 62 ）
动态规划
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
//初始化第一行
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
//初始化第一列
for (int i = 0; i < m; i++) {
dp[i][0] = 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];
}
}
方法二：动态规划 优化空间复杂度
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];//保存上一行的每个位置的结果
//初始化第一行
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
for (int i = 1; i < m; i++) {
int left = 1;//保存当前位置左侧的数值
for (int j = 1; j < n; j++) {
dp[j] = left + dp[j];
left = dp[j];
}
}
return dp[n - 1];
}
}
5.不同路径II（ LeetCode 63 ）
动态规划
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
if (obstacleGrid[0][0] == 1)return 0;//特殊情况，第一个元素处就堵塞
dp[0][0] = 1;//边界条件
//初始化第一行
for (int i = 1; i < n; i++) {
if (obstacleGrid[0][i] == 1){
//此处不通直接置0
dp[0][i] = 0;
}else {
dp[0][i] = dp[0][i - 1];//等于前一处的方案数
}
}
//初始化第一列
for (int i = 1; i < m; i++) {
if (obstacleGrid[i][0] == 1){
dp[i][0] = 0;
}else {
dp[i][0] = dp[i - 1][0];
}
}
//计算其他行
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1){
dp[i][j] = 0;
}else {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];//转移方程
}
}
}
return dp[m - 1][n - 1];
}
}
方法二：动态规划
优化空间复杂度
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] dp = new int[n];//某一行中的元素对应的路径数
if (obstacleGrid[0][0] == 1)return 0;
dp[0] = 1;
//初始化第一行
for (int i = 1; i < n; i++) {
if (obstacleGrid[0][i] == 1){
dp[i] = 0;
}else {
dp[i] = dp[i - 1];
}
}
for (int i = 1; i < m; i++) {
//首元素单独计算
if (obstacleGrid[i][0] == 1){
dp[0] = 0;
}
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1)
dp[j] = 0;
else
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
}
边栏推荐
猜你喜欢
LeetCode 1351. Counting Negative Numbers in Ordered Matrices (Simple)
Convolutional Neural Network (CNN) for mnist handwritten digit recognition
LeetCode 162. Finding Peaks (Moderate)
【C语言】结构体变量学习笔记1
卷积神经网络(CNN)实现服装图像分类
Convolutional Neural Network (CNN) for Clothing Image Classification
STM32单片机手机APP蓝牙高亮RGB彩灯控制板任意颜色亮度调光
多线程与多进程（概念详细讲解）
【目标检测】相关指标的引入与解析
VTK 初步 (1) ----- 可视化管线
随机推荐
电镀废水除六价铬
STM32F407ZG GPIO输出相关实验
氨氮吸附工艺
2021-04-15 jacoco代码覆盖率统计和白盒测试
详解样条曲线（上）（包含贝塞尔曲线）
自定义View的流程总结学习
深度学习阶段性报告（一）
LeetCode 100. The same tree (simple)
Convolutional Neural Network (CNN) for mnist handwritten digit recognition
LeetCode 162.寻找峰值（中等）
LeetCode 292.Nim 游戏（简单）
在Unity中判断游戏物体是否在游戏屏幕范围之内
STM32F407ZG GPIO输入相关实验
详解 Hough 变换（上）基本原理与直线检测
LeetCode 94. Inorder Traversal of Binary Trees (Simple)
Common class String overview
51单片机营养液自动配置搅拌系统TDS浓度采集自动加水加营养液
LeetCode 面试题17.14 最小k个数（中等）
STM32F407ZG 看门狗 IWDG ＆ WWDG
R语言聚类分析——代码解析