Top 150 · 一维动态规划（5 题）
线性 DP：爬楼梯、打家劫舍、零钱兑换与 LIS。
本模块共 5 题，属于 LeetCode 面试经典 150 题 系列。
70. 爬楼梯
难度： 简单
力扣做题思路
代码
class Solution {
public int climbStairs(int n) {
if(n == 1){
return 1;
}
int[] stairs = new int[n];
stairs[0] = 1;
stairs[1] = 2;
for (int i = 2; i < n; i++) {
stairs[i] = stairs[i-1] + stairs[i-2];
}
return stairs[n-1];
}
}复杂度
- 时间：
- 空间：
备注
198. 打家劫舍
难度： 中等
力扣做题思路
代码
class Solution {
public int rob(int[] nums) {
int[] max = new int[nums.length];
int len = nums.length;
if(len == 1){
return nums[0];
}
if(len == 2){
return Math.max(nums[0],nums[1]);
}
max[0] = nums[0];
max[1] = Math.max(nums[0],nums[1]);
for (int i = 2; i < len; i++) {
max[i] = Math.max(max[i-2]+nums[i],max[i-1]);
}
return max[len-1];
}
}复杂度
- 时间：
- 空间：
备注
139. 单词拆分
难度： 中等
力扣做题思路
dp[i] 代表前i个可以用字典中的表达
代码
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
boolean[] dp = new boolean[len+1];
dp[0] = true;
for (int i = 0; i < len; i++) {
if(dp[i]){
for (int j = 0; j < wordDict.size(); j++) {
if(i+ wordDict.get(j).length() > len){
continue;
}
if(s.startsWith(wordDict.get(j),i)){
dp[i+wordDict.get(j).length()] = true;
}
}
}
}
return dp[len];
}
}复杂度
- 时间：
- 空间：
备注
322. 零钱兑换
难度： 中等
力扣做题思路
dp[i]代表金额i可以用最少几个coin表示
代码
class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[] dp = new int[amount+1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
int min = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) {
if(i-coins[j] <0 || dp[i - coins[j]] == Integer.MAX_VALUE) continue;
min = Math.min(dp[i-coins[j]]+1,min);
}
dp[i] = min;
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}复杂度
- 时间：
- 空间：
备注
300. 最长递增子序列
难度： 中等
力扣做题思路
dp[i]代表到自己的递增子序列有几个
代码
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if(n ==1){
return 1;
}
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ans = 1;
for (int i = 1; i < n; i++) {
int max =1;
for (int j = 0; j < i; j++) {
if(nums[j] < nums[i]){
max = Math.max(max, dp[j] + 1);
}
}
dp[i] = max;
ans = Math.max(dp[i] , ans);
}
return ans;
}
}复杂度
- 时间：
- 空间：
备注
二分+贪心的nlogn做法
维护一个数组tails，tails[i]表示长度为i+1的递增子序列的最小结尾元素
每次来一个新数x：x比tails所有数都大 → 直接追加，长度+1;否则 → 二分找到第一个>=x的位置，替换掉
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0; // tails的有效长度
for (int x : nums) {
// 二分找第一个>=x的位置
int left = 0, right = size;
while (left < right) {
int mid = (right-left)/2+left;
if(tails[mid]< x){
left = mid +1;
}else{
right = mid;
}
}
tails[left] = x; // 替换或追加
if (left == size) size++; // 追加了新元素
}
return size;
}
}