动态规划
基础知识
递归(dfs)->记忆化搜索(cache存dfs)->递推(dp)
题目分类:
动态规划,英文:Dynamic Programming,简称 DP,如果某一问题有很多重叠子 问题,使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的,
动态规划的三要素:
- 最优子结构
- 状态转移方程((包含最优子结构))
- 边界
509. 斐波那契数
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你 n ,请计算 F(n) 。
解答:
class Solution {
public int fib(int n) {
if(n == 0) return 0;
if(n <= 2) return 1;
int[] dp = new int[2];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++){
int temp = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = temp;
}
return dp[1];
}
}
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
解答:
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i < n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
}
746. 使用最小花费爬楼梯
旧题目描述:
数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。
每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。
解答:
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length+1];
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i < dp.length; i++){
dp[i] = Math.min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1]);
}
return dp[dp.length-1];
}
}