动态规划 - 以最长回文子串为例 about basic-programming-knowledge HOT 6 CLOSED

// 常规递增
// dp[i][j] 表示i楼j个蛋的最坏情况尝试次数
function egg(K, N) {
  let dp = new Array(N + 1).fill(0).map(() => new Array(K + 1).fill(0));

  for (let i = 1; i <= N; i++) dp[i][1] = dp[i - 1][1] + 1;
  for (let i = 1; i <= K; i++) dp[1][i] = 1;

  for (let k = 2; k <= K; k++) {
    for (let n = 2; n <= N; n++) {
      // 两个方向累积的和
      let min = Number.MAX_SAFE_INTEGER;
      for (let x = 1; x <= n; x++) {
        let max = 1 + Math.max(dp[x - 1][k - 1], dp[n - x][k]);
        if (max < min) {
          min = max;
        }
      }
      dp[n][k] = min;
    }
  }

  return dp[N][K];
}

// 一维数组dp[i]表示i个蛋的最坏尝试次数，大于等于N时截止
function egg2(K, N) {
  // k个鸡蛋最坏扔的次数，最坏次数不会超过N，因为可以用一个鸡蛋从0 开始到N依次扔
  let dp = new Array(K + 1).fill(0);
  let cnt = 0;
  while (dp[K] < N) {
    cnt++;
    for (let i = K; i > 0; i--) {
      dp[i] = dp[i - 1] + dp[i] + 1;
    }
  }
  console.log('egg2', cnt);
  return cnt;
}

// 二分策略
// dp[i][j]表示i楼j个蛋的尝试次数。他等于dp[i - 1][j - 1]的次数加上 dp[i -1][j]的次数，再加上本次尝试的1
// dp[i][j] 也表示目标为i的情况，j个蛋的尝试次数
function egg3(K, N) {
  let dp = new Array(N + 1).fill(0).map(() => new Array(K + 1).fill(0));

  for (let n = 1; n <= N; n++) {
    for (let k = 1; k <= K; k++) {
      dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k] + 1;
      if (dp[n][k] >= N) {
        return n;
      }
    }
  }
  return N;
}

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
  // dp[i]表示i块的最大组合数
  let dp = new Array(amount + 1).fill(0);

  dp[0] = 1
  for (const coin of coins) {
    for (let i = 0; i <= amount; i++) {
      if (i - coin >= 0) {
        dp[i] += dp[i - coin]
      }
    }
  }

  return dp[amount]
};

console.log(change(5, [1,2,5]))

/*
 * @lc app=leetcode.cn id=42 lang=javascript
 *
 * [42] 接雨水
 */
/**
 * @param {number[]} height
 * @return {number}
 */
// 总装水可以拆解为每个凹凼装水 存在几种情况
// 1. 两边高 中间低。标准凹凼
// 2. 中间高 两边低。需要拆分
//   a. 左边整体趋势为拔高。因此可以逐个灌水
//   b. 右边整体趋势为降低。因此可以反向灌水
// 分析了两种情况，其实第1个也可以归结为2.a类型。因为只需要正向一次性灌水就可以完成
// 所以我们采用双向灌水获得最终水量
const trap = function(height) {
  const len = height.length
  if (len <= 2) return 0
  let start = 0
  let end = start + 1
  let water = 0
  // 计算一个区间内的【石头】数量
  function calcStone(height, start, end) {
    let stone = 0
    for (let i = start + 1; i < end; i++) {
      stone = stone + height[i]
    }
    return stone
  }
  // 计算当前区间内装得下的水
  function calcWater (start, end, minValue, stone) {
    return (end - start - 1) * minValue - stone
  }

  // 正向灌水 灌水完毕后有两种情况
  // 1 end === len && start < end - 1 说明start比右边都要大，需要反向灌水一次
  // 2 end === len && start === end - 1 说明正向灌水已经满足全部情况
  while (end < len) {
    while (height[end] < height[start]) end++
    // 对应一次灌水完毕的情况(小迭代中)
    if (end >= len) {
      break
    }
    // 计算水量，重置指针
    water = water + calcWater(start, end, height[start], calcStone(height, start, end))
    start = end
    end = start + 1
  }
  // 反向灌水 起始start肯定是比右边所有数字都要大
  if (start < end - 1) {
    end = end - 1
    // 指针反向遍历
    let j = end - 1
    while (j > start) {
      // 每次遇到比后排要大的值 就计算一次区间水量
      while(height[j] <= height[end]) j--
      water = water + calcWater(j, end, height[end], calcStone(height, j, end))
      end = j
      j = end - 1
    }
  }
  return water
}

const arr = [0,1,0,2,1,0,1,3,2,1,2,1] // 6
// const arr = [5, 2, 3, 4] // 3
// const arr = [9, 0, 6, 0, 4, 2, 4] //12
// console.log(trap(arr))

function trap2(nums) {
  let left = [nums[0]];
  for(let i = 1; i < nums.length; i++) {
    left[i] = Math.max(left[i - 1], nums[i])
  }
  let right = [];
  right[nums.length - 1] = nums[nums.length - 1];
  for(let i = nums.length - 2; i >= 0; i--) {
    right[i] = Math.max(right[i + 1], nums[i]);
  }

  let dp = [];
  let max = 0;

  for(let i = 0; i < nums.length; i++) {
    dp[i] = Math.min(left[i], right[i]) - nums[i];
    max += dp[i]
  }

  console.table(dp)
  console.log(max)
  return max
}

trap2(arr)

// 25 10 5 1
// f(x) = f(x - 20) + f(x - 10) + f(x - 5) + f(x - 1)
function coinCountWays(coins, sum) {
  let dp = new Array(sum + 1).fill(0);
 // 核心 起始点。没有硬币也是一种方法
  dp[0] = 1;
  for(let j = 1; j <= sum; j++) {
    for(let i = 0; i < coins.length; i++) {
      if (j - coins[i] >= 0) {
        dp[j] = dp[j] + dp[j - coins[i]];
      }
    }
  }
  console.table(dp)

  return dp[sum]
}

console.log(coinCountWays([25, 10, 5, 1], 5))

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
  if (!text1.length || !text2.length) return 0
  let dp = new Array(text2.length).fill(0);
  for(let i = 0; i < text1.length; i++) {
    // 上一个dp[j]
    let cache = 0;
    for(let j = 0; j < text2.length; j++) {
      let dj = dp[j];
      if (text1[i] === text2[j]) {
        dp[j] = cache + 1;
      } else {
        dp[j] = Math.max(dp[j - 1] || 0, dp[j])
      }
      cache = dj;
    }
  }

  console.table(dp)

  return dp[text2.length - 1];
};

console.log(longestCommonSubsequence('bl', 'yby'))