一开始没看懂dp方程， 举个例子，假如现在我们要求10元所需要的货币， 此时面值有[1，2，4，7，18，22] 显然无法用18和22参与兑换，因此有arr[j]<=i这个限定条件 10元可以  由9元所需货币数加上1元面值 由8元所需货币数加上2元面值 由7元所需货币数加上3元面值 由6元所需货币数加上4元面值 由5元所需货币数加上5元面值 由4元所需货币数加上6元面值 由3元所需货币数加上7元面值 由2元所需货币数加上8元面值 由1元所需货币数加上9元面值  因此，dp[i]=min(dp[i],dp[i−arr[j]]+1)dp[i] = min(dp[i],dp[ i-arr[j...

状态转移方程 dp[i]=Math.max(dp[i],dp[j]+1)dp[i] = Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+1) 条件：j<i且arr[j]<arr[i]j<i且arr[j]<arr[i]j<i且arr[j]<arr[i] function LIS( arr ) { if(arr.length == 0) return 0; let dp = new Array(arr.length); dp[0] = 1; /* *遍历数组中所有的数，再遍历当前数之前的所有数， *只要前面某个...

卡在了第9个测试点 "72910721221427251718216239162221131917242" 为什么错误呢，729107碰到七的时候我直接dp[i] = dp[i-1] + dp[i-2] 实际上nums[i-1]='0'使得dp[i] = dp[i-1] 状态转移方程看代码就可以， function solve( nums ) { let index; for(index=0; index<nums.length; index++) if(nums[index] != '0') break; nums = nums.substring(index,nums.length)...

很简单的dp， 状态转移方程：dp[i][j]=matrix[i][j]+Math.min(dp[i−1][j],dp[i][j−1])dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i][j-1])dp[i][j]=matrix[i][j]+Math.min(dp[i−1][j],dp[i][j−1]) 注意dp的第一行和第一列提前算出 function minPathSum( matrix ) { let dp = new Array(matrix.length) for(let i=0; i<matrix.length; i++) ...

很简单的dp，没什么可以说的，(i,j)一定是由(i,j-1)和(i-1,j)两个地方走出来的， 因此状态转移方程dp[i][j] = dp[i-1][j]+dp[i][j-1] function uniquePaths( m , n ) { let dp = new Array(m); for(let i=0; i<m; i++) dp[i] = new Array(n); for(let i=0; i<m; i++) dp[i][0] = 1; for(let i=0; i<n; i++) dp[0][i] = 1; for(let i=1; i<m; i++){ ...

这里的dp含义和上一次不一样了，最长公共子序列的dp[i][j]表示str1的i位置和st2的j位置截止的最大长度， 而最长公共字串的dp[i][j]表示str1的i位置和str2的j位置作为最后一个元素所构成的最长公共字串，也就是str1的第i个位置必须作为公共子串的最后一个元素，在dp的过程中用index记录最大字串长度的最后一个元素下标 /* 定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。 如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元素所构成的最长公共子串 */ function LC...

这道题我只写出了最长公共子序列的长度，公共子序列实际是什么参考了题解 dp是一个二维数组，行数为s1的长度，列数为s2的长度，首先对与dp[0][]和dp[][0]赋值为0或1，代码的9-15行 状态转移方程：  s1[pi] == s2[j]------>dp[i][j] = dp[i-1][j-1] + 1; s1[pi] != s2[j]------>dp[i][j] = Math.max( dp[i-1][j],dp[i][j-1] )；  想获得公共子序列，参考下图即可，注意如果dp[i][j]=0即可跳出循环，同时要满足i>=0和j>=0 注意：第32行需要...

dp dp 你看我长得像dp吗？ 刚抄了一道题，还是不太懂dp，dp难dp易，dp就是放狗屁，快点去下地 可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为：dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])dp[i]=min(dp[i−1]+cost[i−1],...

function jumpFloor(number) { if(number==1 || number==0) return 1; if(number==2) return 2; return jumpFloor(number-1) + jumpFloor(number-2); }

小技巧：[left,right] = [right,left+right] function Fibonacci(n) { if(n==1 || n==2) return 1; n = n-2; let left=1,right=1; while(n--){ [left,right] = [right,left+right]; } return right; } function Fibonacci(n){ if(n<=2) return 1; return Fibonacci(n-1) + Fibonacci(n-2); }

递归+回溯  创建arr数组存储皇后的摆放情况，初始化为全0 check函数表示当前放置位置是否合法  递归：对于每一行，逐列检查是否合法，合法则在arr数组对应的位置置为1，然后递归 function Nqueen( n ) { let count = 0; let arr = []; for(let i=0; i<n; i++){ arr.push([]); for(let j=0; j<n; j++) arr[i][j] = 0; } function check(row,colomn){//arr[row][colomn]置为1是否合法 for(let i=0; i<...

和全排列一样，甚至更简单，不需要used数组记录使用情况 递归 终止条件：left==n && right==n 本级任务：  左括号没用完，加左括号 左括号<=n并且left>right时，加右括号  不要忘记回溯即可 function generateParenthesis( n ) { let str = ''; let res = []; function traceTrack(left,right){ if(left==n && right==n){ res.push(str); } if(left<n ){ str += '('; ...

和全排列一样，只不过由数组变为了字符串 可以同样用数组path存储，也可以采用字符串存储 数组存储：res.push(path.join('')) 字符串存储： let path = '' path += str[i] path = path.slice(0,path.length-1) function Permutation(str) { let used = []; let path = []; let res = []; function traceTrack(){ if(path.length == str.length){ res.push(path.join('')); retu...

按照56题的思路可能更简单一点，和56题有重复项数字的全排列代码一样 function permute( num ) { let path = []; let res = []; let used = []; function traceTrack(){ //path已经达到num长度时 if(path.length == num.length){ res.push([...path]); return; } for(let i=0; i<num.length; i++){ if(i!=0 && num[i]==num[i-1] && !used[i-1]...