@张昕 said in Easy-To-Understand Recursive DP solution using Java (with explanations):
memorization and memoization.
In computer science -
memoization = memo = value storage
memorization - I'm scratching my head. Someone misspelled memoization?
@张昕 said in Easy-To-Understand Recursive DP solution using Java (with explanations):
memorization and memoization.
In computer science -
memoization = memo = value storage
memorization - I'm scratching my head. Someone misspelled memoization?
Backtracking is slow, but not as slow as O(n^n).
Tried the 3rd one in Python and Java. No TLE. :)
Pathetic.
O(10n) and O(0.1n^{2}) which runs faster asymptotically?
If you use test cases, 1, 2, 3, which runs faster?
You don't really understand what Big-O notation means.
@zzg_zzm said in 7 Lines 59ms Recursive Python Solution:
Actually I favor DFS over DP because DP makes excessive dp[i][j] entries calculations which might not be needed.
DP doesn't necessarily need to be 2-dimension like dp[i][j].
1 dimension can do it all.
def canPartition(self, nums):
def helper(start, target):
dp = [True] + [False] * target
for i in xrange(len(nums)):
for j in xrange(target, nums[i] - 1, -1):
dp[j] = dp[j] or dp[j - nums[i]]
if j == target and dp[j]:
return True
return False
return False if sum(nums) % 2 else helper(0, sum(nums) / 2)
while i < len(ls) and ls[i].isdigit() :
ret = ret*10 + ord(ls[i]) - ord('0')
i += 1
return max(-2**31, min(sign * ret,2**31-1))
This part looks like Java code.
while (i < ls.length() && ls.charAt(i).isDigit()) {
ret = ret * 10 + (ls.charAt(i) - '0');
i++;
}
return Math.max(-2147483648, Math.min(sign * ret, 2147483647))
Let me simplify the answer -
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
str = str.strip()
str = re.findall('^[+\-]?\d+', str)
try:
res = int(''.join(str))
MAX = 2147483647
MIN = -2147483648
if res > MAX:
return MAX
if res < MIN:
return MIN
return res
except:
return 0
Hopefully I'm not overtly simplified the code.
var twoSum = function(nums, target) {
const hmap = {}
for (var id = 0; id < nums.length; id++) {
var deltaId = hmap[target - nums[id]]
if (deltaId !== undefined)
return [deltaId, id]
hmap[nums[id]] = id
}
return []
};