当前位置:网站首页>[JS] - [dynamic planning] - Notes
[JS] - [dynamic planning] - Notes
2022-07-04 23:17:00 【Interesting learning】
【js】-【 Dynamic programming 】- note
1 How to find coins gracefully
Give coins of different denominations coins And a total amount amount. Write a function to calculate the amount needed to make up the total amount least
Number of coins . If no combination of coins can make up the total amount , return -1.
Example 1:
Input : coins = [1, 2, 5], amount = 11
Output : 3
explain : 11 = 5 + 5 + 1
Example 2:
Input : coins = [2], amount = 3
Output : -1
const coinChange = function(coins, amount) {
# It is used to save the minimum number of coins corresponding to each target total
const f = []
f[0] = 0
# Traverse [1, amount] The total amount of coins in this range
for(let i=1;i<=amount;i++) {
# It's the minimum , We assume infinity
f[i] = Infinity
// Loop through the denomination of each available coin
for(let j=0;j<coins.length;j++) {
# If the denomination is less than the target total , Then the problem holds
if(i-coins[j]>=0) {
// State transition equation
f[i] = Math.min(f[i],f[i-coins[j]]+1)
}
}
}
// If the solution corresponding to the target sum is infinite , It means that there is no eligible total number of coins to update it , There is no solution to this problem , return -1
if(f[amount]===Infinity) {
return -1
}
// If there is a solution , Return the content of the solution directly
return f[amount]
};
2 0-1 knapsack problem
Yes n
Item , The volume of the object is called w
Save the array of , The value of an item is called value
Save the array of ; The volume of each article is w[i]
To express , The value of each item is value[i]
To express . There is now a capacity of c
The backpack , Ask how you choose items to put into your backpack , In order to maximize the total value of the items in the backpack ?
Be careful : There are only 1 Pieces of
# Participation is the number of items and the upper limit of the backpack , And an array of weights and values of items
function knapsack(n, c, w, value) {
// dp Is a dynamic planning state saving array
const dp = (new Array(c+1)).fill(0)
# res It is used to record the maximum value in all combination schemes
let res = -Infinity
for(let i=1;i<=n;i++) {
for(let v=c;v>=w[i];v--) {
// Write the equation of state transition
dp[v] = Math.max(dp[v], dp[v-w[i]] + value[i])
// Update the maximum value immediately
if(dp[v] > res) {
res = dp[v]
}
}
}
return res
}
3 Longest ascending subsequence model
Title Description : Given an unordered array of integers , Find the length of the longest ascending subsequence .
Example :
Input : [10,9,2,5,3,7,101,18]
Output : 4
explain : The longest ascending subsequence is [2,3,7,101], Its length is 4.
var lengthOfLIS = function(nums) {
if(!nums.length) return 0;
# Initialize the status value of each index bit in the array
const dp= new Array(nums.length).fill(1);
let res =1;
for(let i=1;i<nums.length;i++){
for(let j=0;j<i;j++){
# If you encounter a value smaller than the current element , It means that an ascending subsequence that can be extended , Therefore, update the status corresponding to the index bit of the current element
if(nums[j]<nums[i]) dp[i]=Math.max(dp[i],dp[j]+1);
}
res= Math.max(dp[i],res);
}
return res;
};
边栏推荐
猜你喜欢
A complete tutorial for getting started with redis: Pipeline
vim编辑器知识总结
Observable time series data downsampling practice in Prometheus
Font design symbol combination multifunctional wechat applet source code
D3.js+Three. JS data visualization 3D Earth JS special effect
[graph theory] topological sorting
JS 3D explosive fragment image switching JS special effect
C language to quickly solve the reverse linked list
【剑指offer】1-5题
One of the commonly used technical indicators, reading boll Bollinger line indicators
随机推荐
QT drawing network topology diagram (connecting database, recursive function, infinite drawing, dragging nodes)
Advantages of Alibaba cloud international CDN
【ODX Studio编辑PDX】-0.3-如何删除/修改Variant变体中继承的(Inherited)元素
One of the commonly used technical indicators, reading boll Bollinger line indicators
Summary of wechat applet display style knowledge points
A complete tutorial for getting started with redis: getting to know redis for the first time
【ODX Studio編輯PDX】-0.2-如何對比Compare兩個PDX/ODX文件
智力考验看成语猜古诗句微信小程序源码
Phpcms paid reading function Alipay payment
该如何去选择证券公司,手机上开户安不安全
P2181 diagonal and p1030 [noip2001 popularization group] arrange in order
Redis introduction complete tutorial: detailed explanation of ordered collection
[ODX studio edit PDX] - 0.2-how to compare two pdx/odx files of compare
PS style JS webpage graffiti board plug-in
LIst 相关待整理的知识点
Ffmpeg quick clip
【js】-【排序-相关】-笔记
Basic knowledge of database
Explanation of bitwise operators
Notepad++ -- editing skills