https://leetcode.cn/problems/house-robber-iii/?envType=study-plan-v2&envId=dynamic-programming
缓存秒了，看了答案才理解题意就知道怎么写了...
这个题问写的太误导人了
```js
var rob = function (root) {
const fCache = new Map();
const gCache = new Map();
const f = (root) => {
if (root == null) {
return 0;
}
if(fCache.has(root)){
return fCache.get(root)
}
const fResult = g(root.left) + g(root.right) + root.val;
fCache.set(root, fResult);
return fResult;
};
const g = (root) => {
if (root == null) {
return 0;
}
if(gCache.has(root)){
return gCache.get(root)
}
const gResult = Math.max(
g(root.left) + g(root.right),
g(root.left) + f(root.right),
f(root.left) + g(root.right),
f(root.left) + f(root.right)
);
gCache.set(root, gResult);
return gResult;
};
const dfs = (root) => {
const r1 = f(root);
const r2 = g(root);
return Math.max(r1, r2);
};
return dfs(root);
};
```
https://leetcode.cn/problems/coin-change-ii/submissions/568515820/?envType=study-plan-v2&envId=dynamic-programming
一开始过于在乎局部的递归，没扣好缓存
```js
var change = function (amount, coins) {
const cache = new Map()
const dfs = (amount, pos) => {
if (amount == 0) {
return 1
}
if (amount < 0) {
return 0
}
if (pos >= coins.length) {
return 0
}
const flag = `${amount} ${pos}`
if (cache.has(flag)) {
return cache.get(flag)
}
let result = undefined
if (amount < coins) {
result = dfs(amount, pos + 1)
} else {
result = dfs(amount, pos + 1) + dfs(amount - coins, pos)
}
cache.set(flag, result)
return result
}
return dfs(amount, 0)
};
```
https://leetcode.cn/problems/coin-change-ii/submissions/568522610/?envType=study-plan-v2&envId=dynamic-programming
转换成二维dp
```js
var change = function (amount, coins) {
const dp = new Array(coins.length + 1).fill(0).map(() => new Array(amount + 1).fill(0))
for (let index = 0; index < dp.length; index++) {
dp = 1
}
for (let index = dp.length - 2; index >= 0; index--) {
for (let mount = 1; mount <= amount; mount++) {
if (mount < coins) {
dp = dp
} else {
dp= dp + dp]
}
}
}
return dp.pop()
};
```
https://leetcode.cn/problems/combination-sum-iv/solutions/2706336/ben-zhi-shi-pa-lou-ti-cong-ji-yi-hua-sou-y52j/?envType=study-plan-v2&envId=dynamic-programming
这题是真没思路，但是看了一眼题解就懂了...
```js
var combinationSum4 = function (nums, target) {
const cache = new Map()
const dfs = (target) => {
if(target==0){
return 1
}
if (cache.has(target)) {
return cache.get(target)
}
let result = 0
for (let index = 0; index < nums.length; index++) {
const num = nums;
if (num <= target) {
result += dfs(target - num)
}
}
cache.set(target, result)
return result
}
return dfs(target)
};
```
https://leetcode.cn/problems/xor-operation-in-an-array/submissions/568601454/?envType=study-plan-v2&envId=primers-list
简单题练练go
```go
func xorOperation(n int, start int) int {
var numArr []int = make([]int, n)
for index, _ := range numArr {
numArr = start + index*2
}
var result int
for _, val := range numArr {
result = result ^ val
}
return result
}
```
https://leetcode.cn/problems/number-of-good-pairs/submissions/568601995/?envType=study-plan-v2&envId=primers-list
秒了！
```go
func numIdenticalPairs(nums []int) int {
var result int;
for ind, val := range nums {
for i := ind + 1; i < len(nums); i++ {
if nums == val {
result++
}
}
}
return result
}
```
https://leetcode.cn/problems/ones-and-zeroes/submissions/568659554/?envType=study-plan-v2&envId=dynamic-programming
缓存dfs秒了！
```js
var findMaxForm = function (strs, m, n) {
strs = strs.map((str) => {
let hasOne = 0;
let hasZero = 0;
for (let index = 0; index < str.length; index++) {
const char = str;
if (char == '1') {
hasOne++;
} else {
hasZero++
}
}
return {
one: hasOne,
zero: hasZero
}
})
const cache=new Map()
const dfs = (pos, m, n) => {
const flag=`${pos} ${m} ${n}`
if(cache.has(flag)){
return cache.get(flag)
}
if (pos >= strs.length) {
return 0
}
let maxLen = 0;
const one = strs.one
const zero = strs.zero
if (m >= zero && n >= one) {
maxLen = Math.max(dfs(pos + 1, m, n), dfs(pos + 1, m - zero, n - one)+1)
} else {
maxLen = dfs(pos + 1, m, n)
}
cache.set(flag,maxLen)
return maxLen
}
return dfs(0, m, n)
};
```
https://leetcode.cn/problems/solving-questions-with-brainpower/submissions/568668652/?envType=study-plan-v2&envId=dynamic-programming
基础dp，贴手秒！
```js
var mostPoints = function (questions) {
const dp = new Array(questions.length).fill(0);
dp = questions;
for (let index = questions.length - 2; index >= 0; index--) {
const question = questions;
const price = question;
const jump = question + index + 1;
const nextValue = jump >= dp.length ? 0 : dp;
dp = Math.max(dp, nextValue + price);
}
return dp;
};
```
https://leetcode.cn/problems/count-ways-to-build-good-strings/?envType=study-plan-v2&envId=dynamic-programming
爬楼梯的题
一开始怎么都不对
然后发现自己没取余
```js
var countGoodStrings = function (low, high, zero, one) {
const cache = new Map()
const dfs = (len) => {
if (cache.has(len)) {
return cache.get(len)
}
if (len == high) {
return 1
}
let result = 0;
if (len + zero <= high) {
result += dfs(len + zero)
}
if (len + one <= high) {
result += dfs(len + one)
}
if (len >= low) {
result += 1
}
result = result % (1000000000 + 7)
cache.set(len, result)
return result
}
return dfs(0)
};
```
https://leetcode.cn/problems/count-good-triplets/submissions/568756318/?envType=study-plan-v2&envId=primers-list
做两道简单题压压惊
```js
func intABS(num int) int {
if num < 0 {
return num * -1
}
return num
}
func countGoodTriplets(arr []int, a int, b int, c int) int {
var result int
for index := 0; index < len(arr); index++ {
for indey := index + 1; indey < len(arr); indey++ {
for indez := indey + 1; indez < len(arr); indez++ {
if intABS(arr-arr) <= a && intABS(arr-arr) <= b && intABS(arr-arr) <= c {
result++
}
}
}
}
return result
}
```