免费网站有哪些,wordpress首页评论,住房和城乡建设部网站注册,南昌做网站哪个公司好目录 动态规划基础斐波那契数爬楼梯使用最小花费爬楼梯 LeetCode 509. 斐波那契数 LeetCode 70. 爬楼梯 LeetCode 746. 使用最小花费爬楼梯
动态规划基础
Dynamic Programming (DP) 如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。
动态规划中每一个状态… 目录 动态规划基础斐波那契数爬楼梯使用最小花费爬楼梯 LeetCode 509. 斐波那契数 LeetCode 70. 爬楼梯 LeetCode 746. 使用最小花费爬楼梯
动态规划基础
Dynamic Programming (DP) 如果某一问题有很多重叠子问题使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的区分于贪心贪心是从局部直接选最优的。
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的
写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。
斐波那契数
class Solution {public int fib(int n) {// dp[i] : 第i 个数的斐波那契数值// 递推公式dp[i] dp[i - 1] dp[i - 2]// 初始化 dp[0] 0;// dp[1] 1;// 遍历顺序: 从前到后// 举例推导 dp 数组: 0 1 1 2 3 5 8 13 21 34 55if (n 1) return n;int[] dp new int[n 1];dp[0] 0;dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}也可以只维护两个元素的数组for 循环里交换一下 :
int sum dp[0] dp[1];
dp[0] dp[1];
dp[1] sum;递归 时间复杂度 O ( 2 n ) O(2^n) O(2n)
class Solution {public int fib(int n) {if (n 1) return n;return fib(n - 1) fib(n - 2);}
}爬楼梯
和斐波那契数列一样dp数组每个值代表爬到第i层楼梯有 dp[i]种方法。
class Solution {public int climbStairs(int n) {// dp[i] 爬到第i层楼梯有 dp[i]种方法// dp[i] dp[i - 1] dp[i - 2] // dp[1] 1dp[2] 2 从i 3 开始递推// 遍历顺序 从前往后// 举例推导 1 2 3 5 8if (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];}
}使用最小花费爬楼梯
class Solution {public int minCostClimbingStairs(int[] cost) {// dp[i] 到达第i台阶所花费的最小体力 // dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);// dp[0] 0; dp[1] 0;// 前序// 举例int[] dp new int[cost.length 1];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];}
}
