动态规划入门 JS

动态规划入门

长话短说，动态规划有很多情景，下面记录一下经典解题思路，最重要的就是数学归纳法？！

BM62 斐波那契数列

也就是f(n)=f(n-1)+f(n-2)，上代码

let number = 8
// 最简单的递归,一旦number==100，那么这个算法会卡死,可以对重复计算的部分进行优化，见进阶篇
function res1(num) {
    
    if (num == 0) {
     return 0 }
    if (num == 1) {
     return 1 }
    return res1(num - 1) + res1(num - 2)
}
console.log(res1(number))

BM64 最小花费爬楼梯

这题也很简单，找出递归关系，f(n)=Min(f(n-1)+cost[n-1]，f(n-2)+cost[n-1] )，上代码，还是一样可能内存溢出

function minCostClimbingStairs(cost) {
    
  // write code here

  if (cost.length == 0) return 0;
  if (cost.length == 1) return 0;

  return Math.min(
    cost[cost.length - 1] + minCostClimbingStairs(cost.slice(0, cost.length - 1)),
    cost[cost.length - 2] + minCostClimbingStairs(cost.slice(0, cost.length - 2))
  );
}
module.exports = {
    
  minCostClimbingStairs: minCostClimbingStairs,
};

BM65 最长公共子序列(二)

这个先放着

BM66 最长公共子串

这个先放着

BM67 不同路径的数目(一)

也很简单，就是f(m,n)=f(m-1,n)+f(m,n-1)，上代码

function uniquePaths(m, n) {
    
  // write code here
  let list = new Array(m).fill(new Array(n).fill(1));
  for (let i = 0; i <= m - 1; i++) {
    
    for (let j = 0; j <= n - 1; j++) {
    
      if (i > 0 && j > 0) {
    
        list[i][j] = list[i - 1][j] + list[i][j - 1];
      }
    }
  }
  return list[m - 1][n - 1];
}
module.exports = {
    
  uniquePaths: uniquePaths,
};