动态规划
核心:画出树形结构图,因为只有画出了树形结构图就知道动态规划到底如何去编写了!!
- 递归 + 缓存:bottom 至 up
# 509.斐波那契数 (opens new window)
题解1:
画出树形结构图,根节点的值由下一层的子节点决定
fib(5) <- fib(4) + fib(3)
一般根据题意决定,
return
的是连续值、离散值需要准备一个缓存矩阵
cache/memo/dp
构造
递归函数
:function recursion()
伪代码:
// 1. 构建缓存矩阵
const cache = [];
// 2. 构造递归函数
function recursion(n){
// 2.1 写递归函数的截止条件
if(return的值是否能通过缓存居中得到?){
若能:直接return [连续值/离散值]
}
// 2.2 递归方程,斐波那契中当前值由下一层字节点决定
cache[n] = recursion(n-1) + recursion(n-2)
// 2.3 递归必须返回结果
return [连续值/离散值]
}
// 3. 返回结果
2
3
4
5
6
7
8
9
10
11
12
13
14
15
点击查看
参考代码
var fib = function(n) {
// 解法1 : 递归 + 缓存
//假装自己已经解决了该问题了: PrendFun(num)
// 缓存区:
const cache = [];
cache[0] = 0;
cache[1] = 1;
function PrendFun(n){
// 递归的截止条件:直接返回已知的值
if(cache[n] !== undefined){
console.log(cache[n]);
return cache[n];
}
// 根据公式自己调用自己
cache[n] = PrendFun(n-1) + PrendFun(n-2);
return cache[n];
}
const result = PrendFun(n);
return result;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
题解2
- 根据递归逻辑,顺序return出各位置上的
value
【此种算法还存在空间优化写法】 - 举例:已知
fib(0)
,fib(1)
,可以此得到fib(2),fib(3),...,f(n)
伪代码
// 1. 先写缓存矩阵
const cache = [];
cache[0] = 0;
cache[1] = 1;
// 2. 按照递归逻辑顺序得值
for(以此编列数组){
以此得到对应的cache[i]
}
// 3. return 结果
2
3
4
5
6
7
8
9
10
点击查看
参考代码
var fib = function(n) {
// 解法2: 自底向上,一个一个算
const cache = [];
cache[0] = 0 ;
cache[1] = 1 ;
for (let i=2;i<=n;i++){
cache[i] = cache[i-1]+cache[i-2];
}
return cache[n];
};
2
3
4
5
6
7
8
9
10
# 55.跳跃游戏 (opens new window)
题解1:
斐波那契的离散版本
cache/memo
直接三个值:0(未知)
、-1(找不到)
、1(找到)
难点:画出树形结构图
- 子节点全为
-1
,则根节点为-1
- 只要有一路
1
,则根节点为1
- 子节点全为
伪代码:
// 1.构建缓存矩阵与设置初始条件
const memo = [];
memo[end结点] = -1;
// 2.递归函数:
function recursion(n){
//2.1 截止条件
if(return的值是否能通过缓存居中得到?){
若能:直接return [离散值]
}
//2.2 递归方程
//与斐波那契区别的是,根节点下有多少个子节点不清楚,需要自己去判断start index与end index
for(let i=start index;i<end index;i++){
递归调用 recursion(i),只要根节点有1,则直接return 1
}
否则,memo[当前节点] = -1
return false
}
// 返回结果
return jump(0)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
点击查看
参考代码
var canJump = function(nums) {
const totalLength = nums.length;//区别 Fib函数并没有预存空间
const memo = Array(totalLength).fill(0);
memo[totalLength - 1] = 1 ;// 这步类似fib函数
// 递归函数:
function jump(position){
// 截止条件
if(memo[position] === 1){
return true;
}else if(memo[position] === -1){
return false;
}
// 递归方程,主要是解决0的情况
const maxJump = Math.min(position + nums[position], totalLength-1);
for(let i = position+1;i<=maxJump;i++){
const jumpResult = jump(i);
if(jumpResult === true){
memo[position] = 1;
return true;
}
}
memo[position] = -1;
return false;
}
let result = jump(0);
return result;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
题解2:
- 同斐波那契序列,根据递归逻辑,顺序return出各位置上的
value
,只不过跳跃游戏中该value比较隐式- 首先,定义
return
的value
有两类:0 和 1 - 起始点:
memo[end] = 1
,依次迭代可得memo[end-1]
,memo[end-2]
,......,memo[0]
- 直接
return memo[0]
- 首先,定义
伪代码:
//1. 缓存矩阵及初始值
const memo = [];
memo[end] = 1 ;
//2. 从后往前顺序计算memo
for(从后往前计算,end-1,end-2,...,0){
// 计算根节点,因为不同于斐波那契函数,此根节点的数目不确定
for(根节点循环){
if(一旦memo中存在1){
//1.设置当前位置的memo[i]为1
//2.找到以后就无序再找了,所以直接break就可以了。
}
}
}
//3. return memo[0] 从缓存矩阵中读取
2
3
4
5
6
7
8
9
10
11
12
13
14
15
点击查看
参考代码:
var canJump = function(nums) {
const memo = Array(nums.length).fill(0);
memo[nums.length - 1] = 1;
for(let i = nums.length-2;i>=0;i--){
const maxJump = Math.min(nums.length-1, nums[i]+i);
for(let j=i+1;j<=maxJump;j++){
if(memo[j] === 1){
memo[i] = 1;
break;
}
}
}
// 这里memo状态只需要1和0,无序要设置-1,所以memo返回的矩阵[0 0 0 1]等
if(memo[0]==1){
return true
}else{
return false
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 70.爬楼梯 (opens new window)
题解:
- 基本理解了斐波那契数列那道题,此题就可以轻松解决。
- 区别是:cache缓存矩阵的大小
- 可以是空矩阵,截止条件判断cache矩阵中是否已有缓存值【
!== undefined
】 - 也可以提前设置一个大小已知的矩阵
Array(n).fill(0 or null)
,截止条件判断cache矩阵中是否已有缓存值【!== null
】
- 可以是空矩阵,截止条件判断cache矩阵中是否已有缓存值【
点击查看
参考代码:
- 递归 + 缓存
var climbStairs = function(n) {
// 递归 + 缓存版本
const cache = [];
cache[1] = 1;
cache[2] = 2;
function f(n){
if( cache[n] != undefined ){
return cache[n]
}
// 未定义就要计算
cache[n] = f(n-1) + f(n-2);
return cache[n];
}
return f(n);
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- 按照缓存方向顺序迭代
var climbStairs = function(n) {
// 按照缓存方向顺序迭代,设置初始迭代值
const cache = [];
cache[1] = 1;
cache[2] = 2;
for(let i=3;i<=n;i++){
cache[i] = cache[i-1] + cache[i-2];
}
return cache[n];
};
2
3
4
5
6
7
8
9
10
11
- 继续优化空间,已知下一个位置只需要两个变量可得,那就只开两个变量缓存中间值。
var climbStairs = function(n) {
// 按照缓存方向顺序迭代[双变量缓存版]
pre = 1;
cur = 2;
for(let i=3;i<=n;i++){
cur2 = pre + cur;
pre = cur;
cur = cur2;
}
if(n==1 || n==2){
return n
}else{
return cur
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 198.打家劫舍 (opens new window)
题解:
非常简单的一道题
cache
保存各位置能偷到的最大利润,更新原则:当前的最大利润 = 当前值 + Math.max(前隔一个位置以前利润的最大值)MaxProfit
存放前隔一个位置以前利润的最大值。
点击查看
参考代码:
var rob = function(nums) {
if(nums.length<1){
return nums.length
}else if(nums.length==1 ){
return nums[0]
}else if(nums.length==2){
return Math.max(...nums)
}
const cache = Array(nums.length);
cache[0] = nums[0];
cache[1] = nums[1];
maxProfit = nums[0];
for(let i =2;i<nums.length;i++){
cache[i] = maxProfit + nums[i];
maxProfit = Math.max(cache[i-1], maxProfit);
};
// console.log(cache)
return Math.max(...cache);
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 238.除自身以外数组的乘积 (opens new window)
题解:
- 知识点:
两遍动态规划
- 第1遍:
cache
存放的是从左至[当前位置-1]的乘积 - 第2遍:
cache
存放的是从右至[当前位置+1]的乘积
伪代码:
// 定义缓存矩阵 result
// 原矩阵:product=1 -> [1,2,3,4]
// 第一遍动态规划:[1,1,2,6] <- product=1
// 第二遍动态规划:[24,12,8,6] -> return
2
3
4
点击查看
参考代码:
var productExceptSelf = function(nums) {
const result = Array(nums.length).fill(1);
let product = 1;
for(let i=0;i<nums.length;i++){
// 1 [1,1,1,1];
// product 记录的是前一个值的乘积
result[i] = product * result[i];
product = product * nums[i]; // product 更新
}
product = 1;
for(let i=nums.length-1;i>=0;i--){
// 1 [1,1,1,1];
// product 记录的是前一个值的乘积
result[i] = product * result[i];
product = product * nums[i]; // product 更新
}
return result ;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 53.最大子序列和 (opens new window)
题解:
循环遍历一次数组,记录每个索引值上的最大的数组和。
最大值求解规则:
如:[-2,1,-3,4,-1,2,1,-5,4] 缓存中间的最大值: [-2,1,-2,4,3,5,6,1,5] 动态规划问题: 状态转移方程:当前最大值 = max(前值最大值 + 当前值,当前值)
1
2
3
4
5
点击查看
参考答案:
var maxSubArray = function(nums) {
// 上一个值的最大值
let memo = 0;
// 缓存中间结果
let max = nums[0];
for(let i=0 ;i<nums.length;i++){
memo = Math.max(memo + nums[i] , nums[i]);
max = Math.max(max,memo);
}
return max
};
2
3
4
5
6
7
8
9
10
11
12
# 152.乘积最大子数组 (opens new window)
题解:
- 思路同同53题最大子序列和,唯一不同的时候,需要负数存在的情况
- 缓存矩阵的思考
cache1
存当前位置以前的最大值cache2
存当前位置以前的最小值【负数情况】- 两个缓存矩阵交替决定:
nums[i]
、cache1[i] * nums[i]
、cache2[i] * nums[i]
伪代码:
// 先决定cache1[0],cache2[0]
for(从i=1开始遍历数组){
更新cache1
更新cache2
}
return cache1中的最大值
2
3
4
5
6
点击查看
参考代码:
- 自底向上,顺序决定递归值
var maxProduct = function(nums) {
let cache1 = [];// cache1 保存当前位置的最大乘积
cache1[0] = nums[0];
let cache2 = [];// cache1 保存当前位置的最小乘积
cache2[0] = nums[0];
for(let i=1;i<nums.length;i++){
cache1[i] = Math.max(cache1[i-1] * nums[i], cache2[i-1] * nums[i], nums[i]);
cache2[i] = Math.min(cache1[i-1] * nums[i], cache2[i-1] * nums[i], nums[i]);
}
return Math.max(...cache1);
};
2
3
4
5
6
7
8
9
10
11
同样该动规问题可以由
递归+缓存
决定recursionMax(n) 返回的是当前乘积的最大值【根】<--
recursionMax(n-1)
、recursionMin(n-1)
、nums[n]
【叶】
var maxProduct = function(nums) {
if(nums.length == 1){
return nums
}
// 缓存矩阵
const memoMax = Array(nums.length).fill(null);
const memoMin = Array(nums.length).fill(null);
memoMax[0] = nums[0];
memoMin[0] = nums[0];
var result = nums[0];
// 最大递归函数
function recursionMax(n){
if(memoMax[n] != null){
return memoMax[n]
};
// 转移方程
memoMax[n] = Math.max(recursionMax(n-1)*nums[n],nums[n],recursionMin(n-1)*nums[n]);
result = Math.max(result, memoMax[n]);
return memoMax[n];
}
function recursionMin(n){
if(memoMin[n] != null){
return memoMin[n]
};
memoMin[n] = Math.min(recursionMax(n-1)*nums[n],nums[n],recursionMin(n-1)*nums[n]);
return memoMin[n];
}
recursionMax(nums.length-1);
return result;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 62. 不同路径
题解:
- 知识点:
二维动态规划
点击查看
参考代码:
- 递归 + 缓存
var uniquePaths = function(m, n) {
// js中二维空矩阵的创建:
memo = [];
// 矩阵的创建:通过数组实现,索引[行][列]
for(let i=0;i<m;i++){
memo.push(Array(n).fill(0));
};
for(let i = 0; i<m ;i++){
memo[i][0] = 1;
};
for(let j = 0; j<n ;j++){
memo[0][j] = 1;
};
// 编写递归函数
function recurision(m,n){
// 截止条件
if( memo[m-1][n-1] !== 0 ){
return memo[m-1][n-1]
}
memo[m-1][n-1] = recurision(m-1,n) + recurision(m,n-1);
return memo[m-1][n-1];
}
return recurision(m,n);
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
- 顺序迭代
var uniquePaths = function(m, n) {
// js中二维空矩阵的创建:
memo = [];
// 矩阵的创建:通过数组实现,索引[行][列]
for(let i=0;i<m;i++){
memo.push(Array(n).fill(0));
};
for(let i = 0; i<m ;i++){
memo[i][0] = 1;
};
for(let j = 0; j<n ;j++){
memo[0][j] = 1;
};
// 自底向上递归
for(let i=1;i<m;i++){
for(let j=1;j<n;j++){
memo[i][j] = memo[i-1][j] + memo[i][j-1];
}
}
return memo[m-1][n-1]
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 121.买卖股票的最佳时机 (opens new window)
题解:
此题:看似非动态规划,实为动规。
此题为简单题,若一开始没有想通,其实也很好编写出来,但是一旦相同了是动规问题,则可直接套用动规的模板写法,思路清晰简介。
点击查看
参考代码:
- 模板写法,只要掌握了标准写法,可随时修改为
递归 + 缓存
版本
var maxProfit = function(prices) {
// 此题:看似非动态规划,实则每一个位置的值仍需要迭代才能确定
// 思考:什么值需要迭代才能知道?minVal[i] <- minVal[i-1], prices[i]
// maxProfit <-- prices[i] - minVal
let maxProfit = 0;
const minVal = [];
minVal[0] = prices[0];
for(let i=1;i<prices.length;i++){
minVal[i] = Math.min(minVal[i-1],prices[i]);
maxProfit = Math.max(maxProfit,prices[i]-minVal[i]);
}
return maxProfit;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
- 思路不清晰版本,
浮动minPrice
var maxProfit = function(prices) {
if(prices.length === 0 ){
return 0;
}
let minPrice = prices[0];
let maxProfit = Array(prices.length).fill(0);
for(let i=1;i<prices.length;i++){
maxProfit[i] = prices[i] - minPrice;
minPrice = Math.min(minPrice, prices[i]);
};
return Math.max(...maxProfit);
}
2
3
4
5
6
7
8
9
10
11
12
# 122.买卖股票的最佳时机 II (opens new window)
题解:
此题虽然是上一题的继承,但是各位置的不存在迭代关系,即
i-1
与i
位置上的数据没有关系故,此题为非动态规划问题
不停地找
peak
和valley
,并将值累加起来
点击查看
参考代码:
var maxProfit = function(prices) {
if (prices.length ===0 ){
return 0;
}
var peak = prices[0];
var valley = prices[0];
var profit = 0;
let i = 0 ;
while( i< prices.length-1){
while(i< prices.length-1 && prices[i]>=prices[i+1]){
i++;
}
valley = prices[i];
while(i< prices.length-1 && prices[i]<=prices[i+1]){
i++;
}
peak = prices[i];
profit += peak - valley;
}
return profit
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 贪心算法
# 134.加油站 (opens new window)
题解:
知识点:
贪心算法
注意点
- 贪心算法大多题目靠背答案,所以如果能用动态规划就尽量用动规,不用贪心算法
核心:变量
currentGas
记录当前节点i
的剩余油量该值 =
i-1
加油站的剩余油量 +i
加油站的添加油量 - 到i
站点花费的油量。这里贪心做的一个操作:对
currentGas
做了一个Relu
激活函数
点击查看
参考代码:
var canCompleteCircuit = function(gas, cost) {
let totalGas = 0;
for(let i=0;i<gas.length;i++){
totalGas += gas[i];
}
let totalCost = 0;
for(let i=0;i<cost.length;i++){
totalCost += cost[i];
}
if(totalGas < totalCost){
return -1;
}
let currentGas = 0;
let start = 0;
for(let i=0;i<gas.length;i++){
currentGas = currentGas - cost[i] + gas[i];
if (currentGas < 0) {
currentGas = 0;
start = i + 1;
}
}
return start;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25