youxiwang

分类

题解(90)

/ 注册

TA的专栏 28篇文章 2人订阅

28篇文章 992人学习

全部文章（共91篇）

题解 | #跳跃游戏(一)# [P0] 来自专栏

假DP 从前往后遍历每一个点，更新目前能跳到的最远的点 import java.util.*; public class Solution { public boolean canJump (int[] nums) { int reach = 0; // 目前最远能跳到的点 ...

Java

2022-02-06

5 558

题解 | JAVA #分割等和子集# [P2] 来自专栏

题目明显可以转化为“是否存在和为sum/2的子数组” 所以就先求和，除以2，得出target sum 定义dp[i][s] 如果dp[i][s]=true, 表示nums[0, i]中存在一个subset的和为s 那么对于第i个数，能凑出s有两种情况： 1. 之前i-1个数已经能凑出s ...

Java

2022-02-06

1 513

题解 | JAVA #打家劫舍(二)# [P2] 来自专栏

跟(一)同样的解法，dp定义也完全不用变。跑两遍而已环形只影响最后一个房子的选择: - 如果偷了第0个房子，那最后一个房子就偷不了。 - 如果不偷第0个房子，那最后一个房子可以选择偷或着不偷那岂不是把两个情况都跑一遍挑个更好的就行了。。。偷了第0个房子：在第1个房子时， g(1...

Java

2022-02-06

2 992

题解 | JAVA #打家劫舍(一)# [P0] 来自专栏

import java.util.*; // F(i): max profit at nums[i], and rob nums[i] // = G(i-1) + nums[i] // G(i): max profit at nums[i], and do not rob nums[i] //...

Java

2022-02-06

0 400

题解 | #目标和# [P3] 来自专栏

时间: O(maxSum*N) 空间: O(maxSum) DP 定义: DP(i, j): # of ways num[0, i] can sum to j. DP(i, j) = DP(i-1, j + num[i]) + DP(i-1, j - num[i]) import jav...

Java

2022-02-02

0 337

题解 | #三角形最小路径和# [P0] 来自专栏

从下往上dp f(i,j) = Min{f(i+1,j), f(i+1,j+1)} + v(i,j) O(n^2), O(n^2) TODO: 第二个for-loop倒着走可以空间优化至O(n) import java.util.*; public class Solution { p...

Java

2022-02-01

2 617

题解 | JAVA #买卖股票的最好时机(四)# [P0-T2] 来自专栏

就是三的解法loop个k遍。 profit[k,i]: k次买卖都在0～i天内执行，在第i天手上钱的最大值。对于每个k，profit需要分两部计算 (i.e. buy and sell). 例子, k = 3 price: 3 16 6 14 10 19 pass1-buy:...

Java 动态规划

2022-01-31

2 541

题解 | JAVA O(1) 空间 #买卖股票的最好时机(三)# [P2] 来自专栏

参考的leetcode#123。但是感觉leetcode的O(1)的解法思路有点反人类，就稍微转换了一下。先看(四)的解法再看三(因为四不用空间优化, 好理解)。举例 price: 3 16 6 14 10 19 大致可以理解为把#买卖股票的最好时机(一)#走三遍。第一遍和#买...

Java 动态规划

2022-01-31

1 531

题解 | JAVA DP #买卖股票的最好时机(一)# [P0]

介绍两种时间O(n), 空间O(1)的解法第一种(更符合DP思维): 定义F[i]: 在第i天持有股票的最大浮盈情况1: 第i-1天已经持有股票，那么第i天继续持有的浮盈就是i-1天的浮盈加上i和i-1的价差： F[i-1]+(P[i]-P[i-1]) 情况2: 第i-1天未持有，第i...

Java

2022-01-31

1 343

题解 | JAVA O(1)空间 #最长严格上升子数组(一)# [P2]

首先比较容易会想到需要在dp时每一位考虑用了wildcard和没用wildcard的情况没用wildcare的情况比较简单(见F(i)定义) 用了wildcare的情况为什么要考虑 G(i) 和 H(i)，请看以下案例： 10, 3, 10, 5, 6 G(2)的最优解是[1, 3, 10],...

Java

2022-01-30

0 472