动态规划01
规划 动态 01
2023-09-14 09:16:17 时间
第一题:力扣509题
解题思路:
根据题意,定义动态数组,初始化,递推公式,直接遍历就ok!!!
代码如下:
class Solution {
public int fib(int n) {
//动态规划典型题目
if(n <= 1) {
return n;
}
//1. dp数组
int[] dp = new int[n + 1];
//3. 初始化
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
//2. 递推公式
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
有个类似的题目:力扣70题
解题思路:
和这个题一模一样,要是说不一样,可能就是dp[0]有点争议???
代码如下:
class Solution {
public int climbStairs(int n) {
//类似的一道题目509
if(n <= 2) {
return n;
}
int[] dp = new int[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];
}
}
优化代码如下:
//优化===>维护2个数组就可以了
class Solution {
public int climbStairs(int n) {
//类似的一道题目509
if(n <= 2) {
return n;
}
int[] dp = new int[3];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++) {
int sum = dp[1] + dp[2];
dp[1] = dp[2];
dp[2] = sum;
}
return dp[2];
}
}
该题升级版:力扣746题
解题思路:
比这个题多了一个能量的问题,这个题消耗一次能量可以爬上1或者2层楼梯。
代码如下:
class Solution {
//默认第一个台阶需要花费能量,最后一个台阶不需要
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length];
dp[0] = cost[0];
dp[1] = cost[1];
for(int i = 2; i < cost.length; i++) {
//因为消耗一次能量可以上 1 或者 2 个台阶
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
//既然最后一层不消耗能量,那么,就返回前两个小的那一个
return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}
}
第二题:力扣62题
解题思路:
和之前的题不太一样的地方就是,这里需要维护一个二维数组来解题,其他的思路还是差不多的。
代码如下:
class Solution {
public int uniquePaths(int m, int n) {
//动态规划解题
//二维数组存放结果
int[][] dp = new int[m][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];
}
}
升级版:力扣63题
解题思路:
这个题增加了障碍物,有障碍物就要考虑什么时候更新dp数组了。
代码如下:
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//拿到网格的长和宽
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
//构建新数组
int[][] dp = new int[m][n];
//初始化
for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for(int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {
dp[0][i] = 1;
}
//递推公式
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
//如果有障碍物,不更新dp,继续下一个
if(obstacleGrid[i][j] == 1) {
continue;
}
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
第三题:力扣343题
解题思路:
还是动态规划五大步骤,按照那个来即可!
代码如下:
class Solution {
public int integerBreak(int n) {
//dp[i]为正整数i拆分结果的最大乘积
int[] dp = new int[n+1];
//初始化,体重已给出,n从2开始
dp[2] = 1;
for(int i = 3; i <= n; i++) {
for(int j = 1; j < i; j++) {
//j*(i-j)代表把i拆分为j和i-j两个数相乘
//j*dp[i-j]代表把i拆分成j和继续把(i-j)这个数拆分,取(i-j)拆分结果中的最大乘积与j相乘
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i-j]));
}
}
return dp[n];
}
}
第四题:力扣96题
解题思路:
这题可以参考这个,分析的相当清晰,哈哈!!!
代码如下:
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
//初始化
dp[0] = 1;
//分别让j从1~i取值,j就是头节点
for(int i = 1; i <= n; i++) {
//dp[i] : 1到i为节点组成的二叉搜索树的个数为dp[i]
for(int j = 1; j <= i; j++) {
//dp[j-1] 表示j为头节点的左侧有多少种可能
//dp[i-j] 表示j为头节点的右侧有多少种可能
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}
}
说实话,动态规划问题还是比较难理解的呢,接下来可能还有更难理解的呢,坚持下去!!!
相关文章
- UVA 10739 String to Palindrome(动态规划 回文)
- 62 leetcode 不同路径---动态规划
- [BI项目记]-对项目文件进行规划
- Algorithm:C++语言实现之动态规划算法相关(矩阵连乘状态转移方程、字符串的交替连接、分析格网棋盘的特点、最短路线问题、生产计划问题、动态规划解下列非线性规划)
- 【LINGO】求解二次规划
- “动态规划”这词太吓人,其实可以叫“状态缓存”
- 基于ACO蚁群优化的世界旅行路线规划matlab仿真
- 基于ACO蚁群优化算法的栅格地图避障路线规划matlab仿真
- 剑指 Offer II 095. 最长公共子序列-动态规划算法
- 746. 使用最小花费爬楼梯-动态规划
- [LeetCode] 523. 连续的子数组和 ☆☆☆(动态规划)
- 最长公共子串(动态规划)
- HDU 1505 Largest Rectangle in a Histogram && HDU 1506 City Game(动态规划)
- HCIE-Cloud Computing LAB备考第二步:逐题攻破--第五题:规划--根据创建工程中给的参数,结合网络平面规划表,完成LLD参数规划
- 解锁复杂问题的秘密武器:动态规划算法
- 基于模型预测(MPC)的四轮转向车辆轨迹规划(Matlab代码实现)
- 【无人机】基于MPC的无人机路径规划研究(Matlab代码实现)
- Kafka集群规划
- 数据结构和算法 十九、动态规划