动态规划算法

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤，

第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？

第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。

学过动态规划的可能都经常听到最优子结构，把大的问题拆分成小的问题，说时候，最开始的时候，我是对最优子结构一梦懵逼的。估计你们也听多了，所以这一次，我将换一种形式来讲，不再是各种子问题，各种最优子结构。

第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

由了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

// 题目 1
class People {
  constructor(name) {
    this.name = name
    this.eventMap = {}
  }

  on(eventName, fn) {
    if (this.eventMap[eventName]) {
      this.eventMap[eventName].push(fn)
    } else {
      this.eventMap[eventName] = fn ? [fn] : []
    }
  }
  off(eventName, fn) {
    if (!this.eventMap[eventName]) {
      return
    }
    const fnIndex = this.eventMap[eventName].findIndex(item => item === fn)
    if (fnIndex !== -1) {
      this.eventMap[eventName].splice(fnIndex, 1)
    }
  }
  emit(eventName, ...args) {
    if (Array.isArray(this.eventMap[eventName])) {
      this.eventMap[eventName].forEach(fn => fn(...args))
    }
  }

  sayHi() {
    console.log(`Hi, I am ${this.name}`)
  }
}


/* 以下为测试代码 */
const say1 = (greeting) => {
  console.log(`${greeting}, nice meeting you.`)
}

const say2 = (greeting) => {
  console.log(`${greeting}, nice meeting you, too.`)
}

const jerry = new People('Jerry')
jerry.sayHi()
// => 输出：'Hi, I am Jerry'

jerry.on('greeting', say1)
jerry.on('greeting', say2)

jerry.emit('greeting', 'Hi')
// => 输出：'Hi, nice meeting you.' 和 'Hi, nice meeting you, too'

jerry.off('greeting', say1)
jerry.emit('greeting', 'Hi')
// => 只输出：'Hi, nice meeting you, too'



// 题目 2
const sleep = (duration) => {
  return new Promise((resolve, reject) => {
    let timeout = null;
    try {
      timeout = setTimeout(() => {
        resolve(true)
        clearTimeout(timeout);
      }, duration)
    } catch (e) {
      reject(e)
    }
  })
}

const anyFunc = async () => {
  console.log("123") // 输出 123
  await sleep(300) // 暂停 300 毫秒
  console.log("456") // 输出 456，但是距离上面输出的 123 时间上相隔了 300 毫秒
}

anyFunc()


// 题目 3
const deepGet = (obj, prop) => {
  const regex = /\[(\d+)\]/g
  const replacedStr = prop.replace(regex, '.$1')
  const paramList = replacedStr.split('.')
  for (let i = 0; i < paramList.length; i++) {
    if (!isNaN(paramList[i])) {
      paramList[i] = Number(paramList[i])
    }
  }
  const iterate = (curObj, keyList, keyIndex) => {
    const newObj = curObj[keyList[keyIndex]] ?? undefined
    if (newObj === undefined || keyList.length <= ++keyIndex) {
      console.info(newObj)
      return newObj
    } else {
      iterate(newObj, keyList, keyIndex)
    }
  }
  return iterate(obj, paramList, 0)
}

/** 以下为测试代码 */
deepGet({
  school: {
    student: { name: 'Tomy' },
  },
}, 'school.student.name') // => 'Tomy'

deepGet({
  school: {
    students: [
      { name: 'Tomy' },
      { name: 'Lucy' },
    ],
  }
}, 'school.students[1].name') // => 'Lucy'

// 对于不存在的属性，返回 undefined
deepGet({ user: { name: 'Tomy' } }, 'user.age') // => undefined
deepGet({ user: { name: 'Tomy' } }, 'school.user.age') // => undefined


// 题目 4
const combo = (...args) => {
  const fnList = args.reverse()
  const iterate = (list, index, param) => {
    const res = list[index](param)
    if (list.length > ++index) {
      return iterate(list, index, res)
    } else {
      return res
    }
  }
  return function (value) {
    return iterate(fnList, 0, value)
  }
}

/* 以下为测试代码 */
const addOne = (a) => a + 1
const multiTwo = (a) => a * 2
const divThree = (a) => a / 3
const toString = (a) => a + ''
const split = (a) => a.split('')

split(toString(addOne(multiTwo(divThree(666)))))
// => ["4", "4", "5"]

const testForCombo = combo(split, toString, addOne, multiTwo, divThree)
const testForComboRes = testForCombo(666)
console.info(testForComboRes)
// => ["4", "4", "5"]


// 题目 5
// 开局应该是后手有必胜策略。先从七个球的盘中拿走两个，让两个盘中的状态都保持 5 个，之后就尽力保持两个盘上的数量一致，这样应该能够成功。因为经过测试发现当有一方先导致其中一盘的球数量少于等于两个时，是能够保证他只能拿到最后一个球