光谷做网站,中国建设银行互联网网站,html代码表格,电脑制作ppt的软件JAVA代码编写
动态规划#xff08;Dynamic Programming#xff09;
一个问题可以划分为多个子问题#xff0c;且子问题之间有关联#xff0c;就可以使用动态规划。
动态规划问题步骤#xff1a;
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式…JAVA代码编写
动态规划Dynamic Programming
一个问题可以划分为多个子问题且子问题之间有关联就可以使用动态规划。
动态规划问题步骤
确定dp数组dp table以及下标的含义确定递推公式 dp数组如何初始化确定遍历顺序举例推导dp数组
509. 斐波那契数 斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1给定 n 请计算 F(n) 。 示例 1 输入n 2
输出1
解释F(2) F(1) F(0) 1 0 1示例 2 输入n 3
输出2
解释F(3) F(2) F(1) 1 1 2示例 3 输入n 4
输出3
解释F(4) F(3) F(2) 2 1 3提示 0 n 30
教程https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
方法一动态规划
思路
状态转移方程 dp[i] dp[i - 1] dp[i - 2];
复杂度分析
时间复杂度O(n)空间复杂度O(n)
class Solution {public int fib(int n) {ArrayListInteger f new ArrayList();f.add(0);f.add(1);for(int i 2; in; i){f.add(f.get(i-1)f.get(i-2));}return f.get(n).intValue();}
}class Solution {public int fib(int n) {if (n 1) return n; int[] dp new int[n 1];dp[0] 0;dp[1] 1;for (int index 2; index n; index){dp[index] dp[index - 1] dp[index - 2];}return dp[n];}
}思路
**状态转移方程 dp[i] dp[i - 1] dp[i - 2];**每次都重新赋值a和b这个代码很久以前看过但自己写写不出来。这里的代码空间复杂度小一点因为不需要存储所有的结果。
复杂度分析
时间复杂度O(n)空间复杂度O(1)
class Solution {public int fib(int n) {if (n 2) return n;int a 0, b 1, c 0;for (int i 1; i n; i) {c a b;a b;b c;}return c;}
}方法二递归
思路
状态转移方程 dp[i] dp[i - 1] dp[i - 2];
复杂度分析
时间复杂度O(n)空间复杂度O(n)
class Solution {public int fib(int n) {if(n 2) return n;return fib(n-1)fib(n-2);}
}70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶示例 2
输入n 3
输出3
解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示
1 n 45
教程https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html
方法一动态规划
思路真的很难想到定义
步骤 定义dp数组dp[i] 爬到第i层楼梯有dp[i]种方法 递推公式dp[i] dp[i - 1] dp[i - 2] dp[i - 1]上i-1层楼梯有dp[i - 1]种方法那么再一步跳一个台阶不就是dp[i]了么。dp[i - 2]上i-2层楼梯有dp[i - 2]种方法那么再一步跳两个台阶不就是dp[i]了么。 可以这样理解这边我看了两三遍才理解。因为每次只能走1个楼梯或两个楼梯那么我们要走i个楼梯可以从第i-2个楼梯再走2个楼梯也可以从第i-1个楼梯再走1个楼梯。所以dp[i] dp[i - 1] dp[i - 2] dp数组初始化dp[1]1,dp[2]2 确定遍历顺序:根据递推公式从前往后 举例推导dp数组 就是斐波那契数列。
复杂度分析
时间复杂度O(n)空间复杂度O(n)
class Solution {public int climbStairs(int n) {ArrayListInteger f new ArrayList();f.add(0);f.add(1);for(int i 2; in1; i){f.add(f.get(i-1)f.get(i-2));}return f.get(n1).intValue();}
}746. 使用最小花费爬楼梯
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1
输入cost [10,15,20]
输出15
解释你将从下标为 1 的台阶开始。
- 支付 15 向上爬两个台阶到达楼梯顶部。
总花费为 15 。示例 2
输入cost [1,100,1,1,1,100,1,1,100,1]
输出6
解释你将从下标为 0 的台阶开始。
- 支付 1 向上爬两个台阶到达下标为 2 的台阶。
- 支付 1 向上爬两个台阶到达下标为 4 的台阶。
- 支付 1 向上爬两个台阶到达下标为 6 的台阶。
- 支付 1 向上爬一个台阶到达下标为 7 的台阶。
- 支付 1 向上爬两个台阶到达下标为 9 的台阶。
- 支付 1 向上爬一个台阶到达楼梯顶部。
总花费为 6 。提示
2 cost.length 10000 cost[i] 999
教程https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
方法一动态规划1
思路
步骤 定义dp数组dp[i] 爬到第i层楼梯的最低花费 递推公式dp[i] min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]) dp[i - 1]到i-1层的最低花费dp[i - 1]那么再一步跳一个台阶不就是dp[i]了么那到i的最低花费就是dp[i-1]cost[i-1]。 dp[i - 2]到i-2层的最低花费dp[i - 2]种方法那么再一步跳两个台阶不就是dp[i]了么那到i的最低花费就是dp[i-2]cost[i-2]。 所以递推公式就是dp[i] min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]) dp数组初始化dp[0]0,dp[1]0 确定遍历顺序:根据递推公式从前往后 举例推导dp数组以cost [10,15,20]举例 复杂度分析
时间复杂度O(n)空间复杂度O(n)
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp new int[cost.length1];dp[0] 0;dp[1] 0;for(int i 2; i cost.length; i){dp[i] Math.min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[cost.length];}
}方法二动态规划2
思路
步骤
定义dp数组dp[i] 爬到第i层楼梯的最低花费递推公式dp[i] min(dp[i - 1], dp[i - 2]) cost[i] 到i层楼梯的最低花费可以理解为爬第i层所需的消耗到第i层之前的最低消耗。到第i层之前的最低消耗可以分为dp[i - 1]和dp[i - 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) {dp[i] Math.min(dp[i - 1], dp[i - 2]) cost[i];}//最后一步如果是由倒数第二步爬则最后一步的体力花费可以不用算return Math.min(dp[cost.length - 1], dp[cost.length - 2]);}
}
