2020.2.21每日算法练习

基本动态规划模型

1、数字金字塔：观察下方的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。
------------------------ 13
------------------- 11 ------ 8
-------------- 12 ------ 7 ----- 26
----------- 6 ---- 14 ----- 15 ----- 8
-------12 ---- 7 ----- 13 ----- 24 ---- 11
输出：86

解法1：搜索

let arr = [[13],[11, 8],[12, 7, 26],[6, 14, 15, 8],[12, 7, 13, 24, 11]],
    level = arr.length
function search(x, y) {
  if (x === level-1) return arr[x][y]
  return arr[x][y] + Math.max(search(x+1, y), search(x+1, y+1))
}
search(0, 0)

这可能是最差的方法，像search(1, 0)调用了search(2, 1),search(1, 1)又调用了arr[2][1]，这种方法存在许多重复计算。

解法2：记忆化搜索
受第一种方法启发，用一个数组存储每个节点的结果。

let arrs = [[13],[11, 8],[12, 7, 26],[6, 14, 15, 8],[12, 7, 13, 24, 11]],
    results = []
Array.prototype.initialize = function(sampleArray){ //在Array原型中添加初始化空数组的方法
  for (let element of sampleArray) {
    let temp = []
    for (let num of element) {
      temp.push(0)
    }
    this.push(temp)
  }
}
function maxSum(targetArray, map) {
  let level = targetArray.length, ans
  function search(x, y) {
    if (!map[x][y]) { //map[x][y]为0
      if (x === level-1) map[x][y] = targetArray[x][y] //结果数组最后一行的元素和原数组的一样
      else map[x][y] = targetArray[x][y] + Math.max(search(x+1,y), search(x+1,y+1))
    }
    return map[x][y]
  }
  return ans = search(0, 0)
}
results.initialize(arrs) //结果数组results初始化，大小和arrs一样，只是数字元素都是0
maxSum(arrs, results) //求最长路径

稍微用到点JS的语言特性，不过应该不难理解。

解法3：动态规划（顺推）

let arrs = [[13],[11, 8],[12, 7, 26],[6, 14, 15, 8],[12, 7, 13, 24, 11]], max
for (var i = 1, level = arrs.length; i < level; i++) { //从第二行开始
  for (var j = 0; j <= i; j++) {
    arrs[i][j] += Math.max(arrs[i-1][j-1] || 0, arrs[i-1][j] || 0) //边上的元素可能没有左上或右上元素，这时设缺少的元素为0
  }
}
Math.max(...arrs[level-1])

注意，解法3和解法4都直接用原数组存储计算结果

解法4：动态规划（逆推）

let arrs = [[13],[11, 8],[12, 7, 26],[6, 14, 15, 8],[12, 7, 13, 24, 11]],
    level = arrs.length,
        max
for (let i = level - 2; i >= 0; i--) {
  for (let j = 0; j <= i; j++) {
    arrs[i][j] += Math.max(arrs[i+1][j], arrs[i+1][j+1])
  }
}
arrs[0][0]

2、求最长不下降序列：设有由n个不同的整数组成的数列b(1)，b(2)，···，b(n)。若存在 i1 < i2 < i3 < ··· < ie 且有 b(i1) < b(i2) < b(i3) < ··· <b(ie)，则称为长度为e的不下降序列。求出最长的不下降序列。
输入样例：13，7，9，16，38，24，37，18，44，19，21，22，63，15
输出样例：7，9，16，18，19，21，22，63

思路：从末尾元素开始逆推，15的最长子串是“15”，所以其最长子串长度为1；下个元素63，和15比较，不构成不下降序列，则63的最长子串为“63”，长度为1；下个元素22，依次和63、15比较，发现和63构成不下降序列，于是长度可从63的最长子串长度+1获得，再记录下63在数列中的位置；接着下个元素21...

let arr = [13, 7, 9, 16, 38, 24, 37, 18, 44, 19, 21, 22, 63, 15],
    len = arr.length,
    lengths = new Array(len).fill(1), //长度同arr，元素均为1的数组，用于存放arr中每个元素对应的最长子串长度
    nexts = new Array(len).fill(-1), //长度同arr，元素均为-1的数组，用于存放arr中每个元素的后继元素的坐标
    ans = [], //存放最长子串
    index //用于遍历最长子串

for (let i = len-2; i >= 0; i--) { //从倒数第二个数开始计算
  for (let j = i+1; j < len; j++) { //逐一和其后的元素进行比较
    if (arr[i] < arr[j] && lengths[i] < lengths[j]+1) {
      lengths[i] = lengths[j]+1
      nexts[i] = j
    }
  }
}

index = lengths.indexOf(Math.max(...lengths))
while (index !== -1) { //尽量不要使用while（index），万一index等于0退出循环呢？
  ans.push(arr[index])
  index = nexts[index]
}
console.log(ans)

3、拦截导弹：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种系统有一个缺陷：虽然它的第一次拦截能够到达任意的高度，但以后每一次都不能高于前一次拦截导弹的高度。某天，雷达捕捉到敌国的导弹来袭。因为只有一套系统，所以有可能无法拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹至少需要配备多少套这种导弹拦截系统。
输入样例：389，207，155，300，299，170，158，65
输出样例：6，2

第一问的实现和上题大体相同，只有少许修改，已注明

let arr = [389,207,155,300,299,170,158,65],
    len = arr.length,
    lengths = new Array(len).fill(1),
    nexts = new Array(len).fill(-1),
    ans = []
    index

for (let i = len-2; i >= 0; i--) {
  for (let j = i+1; j < len; j++) {
    if (arr[i] >= arr[j] && lengths[i] < lengths[j]+1) { //修改了比较条件
      lengths[i] = lengths[j]+1
      nexts[i] = j
    }
  }
}

index = lengths.indexOf(Math.max(...lengths))
while (index !== -1) {
  ans.push(arr[index])
  index = nexts[index]
}
console.log(ans.length) //数组长度即所求

第二问采用贪心算法解决。导弹依次飞来，对于每颗导弹，使用能拦截且上次拦截高度最低的系统来拦截。若现有系统都无法拦截，则新增一套系统。代码省略。

4、最短路径：有A、B1-3、C1-3、D1-2、E共10座城市，由A向E单向通行(亦无法通向自己)。用矩阵M表示它们之间的路径长度，第i行第j个元素记为M[i][j]。例如M[1]代表城市B1到各城市的路径长度，M[1][5]代表城市B到城市C2的路径长度，为14（0代表城市之间没有通路）。试用动态规划的最优化原理求出A->E的最短路径及其长度。
00 02 05 01 00 00 00 00 00 00
00 00 00 00 12 14 00 00 00 00
00 00 00 00 06 10 04 00 00 00
00 00 00 00 13 12 11 00 00 00
00 00 00 00 00 00 00 03 09 00
00 00 00 00 00 00 00 06 05 00
00 00 00 00 00 00 00 00 10 00
00 00 00 00 00 00 00 00 00 05
00 00 00 00 00 00 00 00 00 02
00 00 00 00 00 00 00 00 00 00

思路：用Distance(X->Y)代表城市X到城市Y的最短距离
Distance(A -> E) = Min(Distance(B1 -> E), Distance(B2 -> E), Distance(B3 -> E))
Distance(B1 -> E) = Min(Distance(C1 -> E), Distance(C2 -> E)
...
实现：首先处理输入，将字符串转换为符合要求的数组

//跨行字符串
var str = `00 02 05 01 00 00 00 00 00 00
00 00 00 00 12 14 00 00 00 00
00 00 00 00 06 10 04 00 00 00
00 00 00 00 13 12 11 00 00 00
00 00 00 00 00 00 00 03 09 00
00 00 00 00 00 00 00 06 05 00
00 00 00 00 00 00 00 00 10 00
00 00 00 00 00 00 00 00 00 05
00 00 00 00 00 00 00 00 00 02
00 00 00 00 00 00 00 00 00 00`
var arr = []
str.split(/\s/) //切割字符串，得到字符串数组
  .forEach(function(el, index){ //index为当前遍历元素的下标
  if (index % 10 === 0) this.push([]) //到达行首元素，则新建一个子数组
  this[this.length-1].push(Number(el)) //给arr当前的末尾子数组中推入数字
}, arr) //设置this为arr

得到可用的数组arr，开始解题

let distances = [], //长度为10的数组，用于存储10座城市到E城的最短距离，E城到E城距离默认为0
    route = [],
    cities = ['A', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3', 'D1', 'D2', 'E']

function printRoute(arr) { //打印最短路线
  let i = 0,
      route = 'A'
  while (arr[i]) {
    i = arr[i]
    route += ' -> ' + cities[i]
  }
  return route
}

distances[arr.length-1] = 0
route[arr.length-1] = 0

for (let len = arr.length, i = len-2; i >= 0; i--) { //i代表当前正在计算cities[i]到E城的最短路径
  distances[i] = Number.POSITIVE_INFINITY
  for (let j = i+1, len = arr[i].length; j < len; j++) {
    if (!arr[i][j]) continue //跳过0元素
    temp = arr[i][j] + distances[j]
    if (temp < distances[i]) {
      distances[i] = temp
      route[i] = j //记录最短路线中下一个城市在cities数组中的下标
    }
  }
}

console.log(distances[0])
printRoute(route)