算法-JS算法的核心知识

算常数总和-性能好-时间复杂度 O(1)：
飞蛾公式： (n / 2) *(1 + n)

题库：leetcode

• 性能上：for > forEach > map
• for in 是键值的遍历，for of 是 es6 的产物，是迭代器的遍历方式，需要判断遍历对象是否存在
• 本质上 forEach 和 map 是用来遍历 Array
• 反转字符串：str.split(‘’).reduceRight((prev,curr)=>prev+curr)

时/空间复杂度

• 时/空间复杂度

计算时间复杂度？

• 求数字的总和

const numbers = [1, 3, 10, 50]
function sumNumbers(numbers) {
	return numbers.reduce((sum, curNum) => sum + curNum, 0)
}
console.log(sumNumbers(numbers))

//T = 3 + n ==> O(n) ==> Linear Time Complexity ==> 最好的结果，性能好

• 斐波那契数列

// n = 5
function fib(n) {
	const numbers = [1, 1] // 1
	for (let i = 2; i < n + 1; i++) {
		// 1
		console.log('Running') // n-1，可以在循环中写一个log，控制台可以看到它执行多少次
		numbers.push(numbers[i - 2] + numbers[i - 1]) // n-1次
	}
	return numbers[n] // 1
}
// T = 1 + 1 + 1 + 2(n - 1) = 3 + 2n - 2 = 1 + 2n ==> O(n) ==> Linear Time Complexity

• 总结： 使用渐进分析法给每种算法分析以下 3 种情况，最后得到时间复杂度

  • Best Case: number = 1 OR number = 2 => O(1) // 数值少
  • Average Case: O(n)
  • Worst Case: number = 27,277 => O(n) (Improved: O(sqrt(n))) // 数值大

• 判断是否为 2 的幂

  • 使用位运算符：二进制 与 &
  • &： 按位相乘，有 0 为 0,示例：4 & 7 ==> 100 & 111 ==> 100 ==> 4(最终结果)
  • number & (number - 1) === 0: 始终返回 true

function isPowerOfTwo(number) {
	if (number < 1) return false
	return (number & (number - 1)) === 0 // O(1)
}

递归算法

• 阶乘算法

function fact(number) {
	if (number === 1) return 1 // space complexity： 1
	return number * fact(number - 1) // space complexity： 1
}
// 但n次调用的回调函数的时间复杂度是: O(n)
console.log(fact(5)) // 5 * 4 * 3 * 2 * 1
// 空间复杂度：O(n)

• 以递归实现斐波那契数列来证明递归不全是最好的实现方式

  • 问题：建立了一个嵌套树，从 n=4 时会产生多余的相同结果

function fib(n) {
	if (n === 0 || n === 1) return 1
	return fib(n - 1) + fib(n - 2)
	// 每次执行回调函数都有两个函数要执行，表示时间长度是指数级增长
}
// 基于普通循环的时间复杂度为 O(n)
// 基于递归实现的时间复杂度为 O(n^2)

动态编程(Dynamic Programming)

• 在第一个函数也就是该方法的全局中添加存储空间的变量

• 在添加一个记忆变量的形式变量

• 在每次该回调函数结束前，把存储变量赋值给记忆变量

• 判断记忆变量有这个值就返回记忆变量的值不执行后面的内容避免冗余

• 以递归实现的斐波那契为例进行改造

function fib(n, memo) {
	let result
	if (memo[n]) return memo[n]
	if (n === 0 || n === 1) {
		return 1
	} else {
		result = fib(n - 1, memo) + fib(n - 2, memo)
	}
	memo[n] = result
	return result
}
console.log(fib(5, {}))

• 自下而上的方法

建立一个存储所有这些值的存储，将所有结果存储在此存储中的 bonachi 序列。执行方法的过程中，不断生成数据，知道目标值生成完成函数执行。当数据够多，一旦检索到 nf 元素然后我们取消完成函数执行。

• 使用场景：
  1. 在循环中使用底部应用程序方法
  2. 带有递归的动态规划方法

搜索算法

• 线性搜索(可以是任意类型的数据)

  • 从头到尾遍历查找，找到对应的值就返回并停止，只返回第一个目标结果就停止
  • 适用于有序和无序列表，所以列表不必排序
  • 当然可以用系统内置的方法 find(), findIndex()

// 搜索对象
const obj = [
	{ name: 'mary', age: '18' },
	{ name: 'moli', age: '22' },
]
const arr = [5, 3, 10, -10, 33, 51]
function findElement(arr, element, comparatorFn) {
	let index = 0
	for (const item of arr) {
		// item只是临时的，并不依赖数组长度
		if (
			typeof element === 'object' &&
			element !== null &&
			comparatorFn(element, item)
		)
			return index
		if (item === element) return index
		index++ // 只是改变现有的值，并不会返回新值
	}
}
console.log(findElement(arr, 33))
console.log(
	findElement(obj, { name: 'moli', age: '22' }, function (el, it) {
		return el.name === it.name
	})
)
// 空间复杂度为O(1)

• 二分搜索

需要先排序，然后根据中有两边的值，从中间划分查找

1. 基于循环

const arr = [1, 5, 9, 13, 99, 100]
function findElement(sortedArr, element) {
	let startIndex = 0
	let endIndex = sortedArr.length - 1
	while (startIndex <= endIndex) {
		const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2)
		if (element === sortedArr[middleIndex]) return middleIndex
		if (sortedArr[middleIndex] < element) startIndex = middleIndex + 1
		else endIndex = middleIndex - 1
	}
}
console.log(findElement(arr, 9))
// Best Case: 目标刚好正中间 O(1)
// Average Case: 趋于O(log n)
// Worst Case: 目标在开头或结尾 O(log n)

2. 递归的二分查找

const arr = [1, 5, 9, 13, 99, 100]
// sortedArr: 原数组   element： 目标元素   offset：索引偏移量,目标元素在新数组与旧数组的偏差
function findElement(sortedArr, element, offset) {
	let startIndex = 0
	let endIndex = sortedArr.length - 1
	while (startIndex <= endIndex) {
		const middleIndex = Math.floor((endIndex - startIndex) / 2)

		if (element === sortedArr[middleIndex]) return middleIndex + offset // 返回目标元素在原数组的索引：当前元素索引+offest
		if (sortedArr[middleIndex] < element) {
			startIndex = middleIndex + 1
			offset = offset + middleIndex + 1
		} else {
			endIndex = middleIndex
		}
		return findElement(
			sortedArr.slice(startIndex, endIndex + 1),
			element,
			offset
		) // endIndex +1 是为了防止元素出现在最末尾
	}
}
console.log(findElement(arr, 9, 0))
// a: 1 (这里看return那一句时递归的，只执行一次，所以为1)
// b: 2 (这里看切分成多少次，从代码看数组被切分成两次)
// O(n^logb a) => O(n^log2 1) => O(n^0) => O(1)
// overall the algorithms:O(n^logb alog n) => O(1 * log n) => O(log n)

• 与基于循环的解决方案的主要区别： 是在循环中只是改变了索引然后计算不同的中间指标

• 在递归方案中总是计算相同的中间指标，改变 index 来调用新函数，再次使用原始数组的子集。即真的切数组为不同函数调用分成切片，在不同的数组切片上操作

• 主定理(Master Theorem)

• 递归的运行时间： O(n^log_ba)

• 公式里的变量知识面意思?

  • a：等于子问题数（递归拆分数）多久拆分一次数组
  • b：等于相对子问题大小（每次拆分的输入减少）
  • f(n)：等于递归外部运行时，指整个代码

• 使用主定理得到算法的整体时间复杂度的三种情况：

  • case 1：递归步骤，完成最多工作，具有最大的运行时间，算法的运行时间为 O(n^log_ba)
  • case 2：非递归部分做更多工作：O(fn(n))
  • case 3：递归开始时的相同工作量推到整个算法的运行时间 O(n^log_balog n)

排序算法

• 冒泡算法

function sort(arr) {
	const resultArr = [...arr]
	for (let outer = 0; outer < resultArr.length; outer++) {
		let outerEl = resultArr[outer]
		for (let inner = outer + 1; inner < resultArr.length; inner++) {
			let innerEl = resultArr[inner]

			if (outerEl > innerEl) {
				resultArr[outer] = innerEl
				resultArr[inner] = outerEl
				outerEl = resultArr[outer]
				innerEl = resultArr[inner]
			}
		}
	}
	return resultArr
}
const sortedArr = sort([3, 10, -3, 48, 5, 33, 99])

// Best Case: item 已经排序的情况 O(n)
// Average Case: 随机排序，趋于 O(n^2)
// Worst Case: O(n^2)

• 快速排序

function sort(arr) {
	const copiedArr = [...arr]
	if (copiedArr.length <= 1) return copiedArr

	const smElArr = []
	const bigElArr = []
	const pivotEl = copiedArr.shift()
	const centerElArr = [pivotEl] // 中心元素包含枢轴元素

	while (copiedArr.length) {
		const currentEl = copiedArr.shift()
		if (currentEl === pivotEl) centerElArr.push(currentEl)
		else if (currentEl < pivotEl) smElArr.push(currentEl)
		else bigElArr.push(currentEl)
	}
	const smElSortedArr = sort(smElArr)
	const bigElSortedArr = sort(bigElArr)
	return smElSortedArr.concat(centerElArr, bigElSortedArr)
}
const sortArr = sort([-3, 10, 1, 100, -10, 22, 15])
console.log(sortArr)
// 递归步骤的运行时间：O(n^logb a) => O(n^log2 2) => O(n^l) => O(n) // a,b为2是因为最大最小，一共两次
// 递归的外部运行时间：O(n)
// 算法的运行时间：O(n^logb a * log n) => O(n * log n)

• 归并排序

function sort(arr) {
	if (arr.length < 2) return arr
	if (arr.length === 2) return arr[0] > arr[1] ? [arr[1], arr[0]] : arr
	const middle = Math.floor(arr.length / 2)
	const leftArray = arr.slice(0, middle)
	const rightArray = arr.slice(middle) // 从这看出b=2
	const leftSortedArr = sort(leftArray)
	const rightSortedArr = sort(rightArray) // 从这看出时间复杂度a=2，也看出空间复杂度值与数组长度有关
	const mergedArr = []
	let leftArrIndex = 0
	let rightArrIndex = 0
	while (
		leftArrIndex < leftSortedArr.length ||
		rightSortedArr < rightSortedArr.length
	) {
		if (
			leftArrIndex >= leftSortedArr.length ||
			leftSortedArr[leftArrIndex] > rightSortedArr[rightArrIndex]
		) {
			mergedArr.push(rightSortedArr[rightArrIndex])
			rightArrIndex++
		} else {
			mergedArr.push(leftSortedArr[leftArrIndex])
			leftArrIndex++
		}
	}
	return mergedArr
}
const sortedArray = sort([-10, 33, 5, 10, 9, 3, -19, -99, 100])
console.log(sortedArray)
// 时间复杂度：使用主定理推算
// 递归步骤的运行时间： O(n)
// 非递归的运行时间： O(n)
// 整体的运行时间：O(nlogn)

空间复杂度

集合 sets（数组）算法

• 笛卡儿乘积算法

// 衣服制造问题--衣服尺码颜色组合问题
// 只能返回给定两个数组的组合集合
// [['blue','m'],...]
function cartProduct(setA, setB) {
	const product = []
	for (let setAEl of setA) {
		if (!Array.isArray(setAEl)) setAEl = [setAEl]
		for (const setBEl of setB) {
			product.push([...setAEl, setBEl])
		}
	}
	return product
}
// 可以组合多种情况的集合,但要结合上面的函数
// [['blue','m','v neck'], ...]
function cartesian(...sets) {
	let tempProduct = sets[0]
	for (let i = 1; i < sets.length; i++) {
		tempProduct = cartProduct(tempProduct, sets[i])
	}
	return tempProduct
}

const colors = ['blue', 'red']
const sizes = ['m', 'l', 'xl']
const styles = ['round neck', 'v neck']
console.log(cartesian(colors, sizes, styles))
// 时间复杂度： O(n) => O(n^x)
// 空间复杂度： O(n) => O(n^x)

• 全排列 无重复

function getPermutations(options) {
	const permutations = []
	if (options.length === 1) return [options]
	const partialPermutations = getPermutations(options.slice(1))
	const firstOption = options[0]
	for (let i = 0; i < partialPermutations.length; i++) {
		const partialPermutation = partialPermutations[i]
		for (let j = 0; j < partialPermutation.length; j++) {
			const permutationInFront = partialPermutation.slice(0, j)
			const permutationAfter = partialPermutation.slice(j)
			permutations.push(
				permutationInFront.concat([firstOption], permutationAfter)
			)
		}
	}
	return permutations
}
const todoListItems = ['red', 'blue', 'green', 'orange', 'sliver', 'yellow']
console.log(getPermutations(todoListItems))
// 时间复杂度：O(n!) => 4*3*2*1 =24 ,n指的是todoListItems的长度

• 全排列 有重复

function getPermutations(options, length) {
	const permutations = []
	if (length === 1) return options.map((option) => [option])
	const partialPermutations = getPermutations(options, length - 1)

	for (const option of options) {
		for (const existingPermutation of partialPermutations) {
			permutations.push([option].concat(existingPermutation))
		}
	}
	return permutations
}

const digits = [1, 2, 3, 4]
const resultLength = 3 // 生成的子数组不能超过这个长度
console.log(getPermutations(digits, resultLength))
// 时间复杂度： O(n^r)  // n指的是digits的长度，r是生成的子数组的长度

复杂的算法和解决的方法

• 结构化方案

  1. 验证输入的问题
  2. 思考问题和提出解决方案
  3. 编写第一个版本的解决方案
  4. 验证结果
  5. 推到时间复杂度
  6. 探索替代方案

• 背包问题

排列出从所给的 items 中拿出不超过背包重量的 item

function knapsack(items, cap, itemIndex) {
	if (cap === 0 || itemIndex < 0) return { items: [], value: 0, weight: 0 }
	if (cap < items[itemIndex].weight) return knapsack(items, cap, itemIndex - 1)
	const sackWithItem = knapsack(
		items,
		cap - items[itemIndex].weight,
		itemIndex - 1
	)
	const sackWithoutItem = knapsack(items, cap, itemIndex - 1)

	const valueWithItem = sackWithItem.value + items[itemIndex].value
	const valueWithoutItem = sackWithItem.value

	if (valueWithItem > valueWithoutItem) {
		const updateSack = {
			items: sackWithItem.items.concat(items[itemIndex]),
			value: sackWithItem.value + items[itemIndex].value,
			weight: sackWithItem.weight + items[itemIndex].weight,
		}
		return updateSack
	} else {
		return sackWithoutItem
	}
	return {}
}

const items = [
	{ name: 'a', value: 3, weight: 3 },
	{ name: 'b', value: 6, weight: 8 },
	{ name: 'c', value: 10, weight: 3 },
]
const maxCap = 8 // 背包最大容量
const allPermutations = knapsack(items, maxCap, items.length - 1)
console.log(allPermutations)
// time complexity : 2^n

• 改进版

function knapsackFn(items, cap, itemIndex, memo) {
	if (memo[cap][itemIndex]) return memo[cap][itemIndex]
	if (cap === 0 || itemIndex < 0) return { items: [], value: 0, weight: 0 }
	if (cap < items[itemIndex].weight)
		return knapsackFn(items, cap, itemIndex - 1, memo)
	const sackWithItem = knapsackFn(
		items,
		cap - items[itemIndex].weight,
		itemIndex - 1,
		memo
	)
	const sackWithoutItem = knapsackFn(items, cap, itemIndex - 1, memo)
	const valueWithItem = sackWithItem.value + items[itemIndex].value
	const valueWithoutItem = sackWithItem.value

	let resultSack
	if (valueWithItem > valueWithoutItem) {
		const updateSack = {
			items: sackWithItem.items.concat(items[itemIndex]),
			value: sackWithItem.value + items[itemIndex].value,
			weight: sackWithItem.weight + items[itemIndex].weight,
		}
		resultSack = updateSack
	} else {
		resultSack = sackWithoutItem
	}
	memo[cap][itemIndex] = resultSack
	return resultSack
}

// 生成空的数组,from从高的值创建一个新数组, fill不会创建新数组， 这是创建内存的最好方法
function knapsack(items, cap, index) {
	const mem = Array.from(Array(cap + 1), () =>
		Array(items.length).fill(undefined)
	)
	return knapsackFn(items, cap, index, mem)
}

const items = [
	{ name: 'a', value: 3, weight: 3 },
	{ name: 'b', value: 6, weight: 8 },
	{ name: 'c', value: 10, weight: 3 },
]
const maxCap = 8 // 背包最大容量
const allPermutations = knapsack(items, maxCap, items.length - 1)
console.log(allPermutations)
// Time Complexity (without memoization): O(2^n)
// Time Complexity (with memoization): O(2*C) C指的是容量

• 贪心算法 vs 动态算法
  • 解决背包问题的方式： 贪心 和 动态

• 贪心背包算法

// 一次只能返回一个满足要求的选项
function knapsack(elements, capacity) {
	const sack = { items: [], value: 0, weight: 0 }
	let remainingCapacity = capacity
	for (const el of elements) {
		if (el.weight < remainingCapacity) {
			sack.items.push(el)
			sack.value += el.value
			sack.weight += el.weight
			remainingCapacity -= el.weight
		}
	}
	return sack
}
const items = [
	{ name: 'a', value: 3, weight: 3 },
	{ name: 'b', value: 6, weight: 8 },
	{ name: 'c', value: 10, weight: 3 },
]
const maxCap = 8 // 背包最大容量
const sack = knapsack(items, maxCap)
console.log(sack)

• 找零问题

//  存储对象的值
function computeChange(coins, amount) {
	let remainingAmount = amount
	const calculatedChange = {
		selectedCoins: {},
		numberOfCoins: 0,
	}
	for (const coin of coins) {
		const count = Math.floor(remainingAmount / coin)
		calculatedChange[coin] = count
		calculatedChange.numberOfCoins += count
		remainingAmount = remainingAmount - coin * count
	}

	return calculatedChange
}

const availableCoins = [100, 50, 20, 10, 5, 2, 1]
const targetAmount = 50
const change = computeChange(availableCoins, targetAmount)
console.log(change)

• 暴力找零

//  存储对象的值
function computeChange(coins, amount) {
	let remainingAmount = amount
	const calculatedChange = {
		selectedCoins: {},
		numberOfCoins: 0,
	}
	for (const coin of coins) {
		const count = Math.floor(remainingAmount / coin)
		calculatedChange[coin] = count
		calculatedChange.numberOfCoins += count
		remainingAmount = remainingAmount - coin * count
	}

	return calculatedChange
}

function computeChangeBruteForce(coins, amount) {
	const results = []
	for (let i = 0; i < coins.length; i++) {
		results.push(computeChange(coins.slice(i), amount))
	}

	let smallestAmountOfCoins = Number.MAX_SAFE_INTEGER
	let finalResult
	for (const result of results) {
		if (result.numberOfCoins < smallestAmountOfCoins) {
			smallestAmountOfCoins = result.numberOfCoins
			finalResult = result
		}
	}
	return finalResult
}

const availableCoins = [8, 6, 5, 1]
const targetAmount = 83
const change = computeChangeBruteForce(availableCoins, targetAmount)
console.log(change)
// 贪心算法的解决方法的时间复杂度：O(n)
// 暴力算法的解决方法的时间复杂度：O(n^2)

Set 和 new Map

• Set

1. 并集：利用 set 特性给两个数组去重

const arr1 = [1, 22, 38, 31, 18]
const arr2 = [1, 122, 138, 19, 18]
const setArr1 = new Set(arr1)
const setArr2 = new Set(arr2)
const union = newSet([...setArr1, ...setArr2])

2. 交集：

   • const intersection = new Set([...setArr1].filter((item) => setArr2.has(item)))

3. 差集：

   • const intersection = new Set([...setArr1].filter((item) => !setArr2.has(item)))

4. 判断元素是否存在,时间复杂度为 O(1),速度快

const nums = [11, 22, 38, 1, 8]
const newNums = new Set(nums)
console.log(newNums.has(11))

5. 实现队列,队尾添加，队头删除/栈的数据结构，在表尾即可完成添加和删除

const alignment = new Set()
alignment.add(10)
alignment.add(11)
alignment.delete(alignment.values().next().value)

• new Map

// 这种数据结构适用
const result = [
	['iphone4', 19999],
	['ipad', 3999],
	['iMac', 29999],
	['iphone13', 6999],
]
const findPrice = (data, name) => new Map(data).get(name)
finPrice(result, 'iMac')

• Object 与 new Map

• 创建一个 new Map(),可以适用.set(key,value)设置该 Map 的键值，使用.get(key)查找 Map 中该键的值，.has 是否存在该键
• Map 的键值支持正则，Map 是可迭代的，例如：forEach 循环 for…of…循环 ，Object 是不能直接迭代的
• 适用场景：
  1. 当插入的顺序是需要考虑的，并且使用除 String 和 Symbol 以外的键名是，使用 Map
  2. 需要遍历键值对并且需要考虑顺序，优先 Map
  3. 频繁增删改查的场景使用 Map
  4. 表单自定义字段使用 Map

const map4 = new Map()
map4.set('key1', 'value1')
for (const entry of map4) {
}
const object4 = {
	key1: 'value1',
	key2: 'value2',
	key3: 'value3',
}
for (const entry of Object.entries(object4)) {
}

• 元素的顺序和长度

  • Map 保持对长度的跟踪，使其能够在 O(1)复杂度中进行访问
  • Object 想要获得对象的属性长度，需要手动进行迭代，使其文 O(n)复杂度，属性长度为 n
  • Map 始终保持按插入顺序返回键名
  • Object 从 es6 开始，String 和 Symbol 键是按顺序保存起来的，但是通过隐式转换保存成 String 的键是乱序的

• Set 的时间复杂度

  Set 操作	时间复杂度
  Set.prototype.get()	O(1) ~ O(logn)
  Set.prototype.add()	O(1) ~ O(logn)
  Set.prototype.has()	O(1) ~ O(logn)
  Set.prototype.forEach()	O(n)
  Set.prototype.entries()	O(n)
  Set.prototype.values()	O(n)
  Set.prototype.keys()	O(n)

哈希表

• 使用一层循环来获取需要双层循环的结果
• 列举：求两数之和：
  1. 使用 new Map() 创建一个空的 map 数组
  2. 在遍历的过程中通过 map 数组使用 has 方法判断 target-数组中的某一项得到的值是否存在
     • 存在就使用 get 方法获取对应值的小标并返回
     • 不存在就使用 set 方法设置下标给 map 数组
  3. 如果把 for 循环换成 forEach 有问题

var twoSum = function (nums, target) {
	const map = new Map() // 创建一个空映射
	for (let i = 0; i < nums.length; i++) {
		if (map.has(target - nums[i])) {
			// 这个存在适当，map将两个符合要求的结果都已经存储的情况下执行的
			return [map.get(target - nums[i]), i]
		}
		map.set(nums[i], i) // 遍历第一回肯定不存在，就将键值添加到map中
	}
}

回溯算法

• 本质：暴力穷举算法
• 列如：给定两个整数 n 和 k，返回范围[1,n]中所有可能的 k 的组合，不要求顺序
• 其中：k 指的是组合的长度，如[2,4],并且按照数学规范[最小值，最大值]， n 指最大区间

const combine = (n, k) => {
	const ans = []
	const getAns = (val, arr) => {
		arr.push(val) // 将获取到的值添加到数组中，并计算如果数组长度和k的长度一样就直接添加到对应数组中
		if (arr.length === k) {
			ans.push(arr)
			return
		}
		if (n - val < k - arr.length) return //  n-val < k-arr.length ,是控制组合的展示形式符合数学规范，并且最大值不在选择范围
		for (let i = val + 1; i <= n; i++) {
			// 如果长度不满足就再次进入循环知道满足
			getAns(i, [...arr])
		}
	}
	for (let i = 1; i <= n - k + 1; i++) {
		getAns(i, []) //  传一个空数组，用来存储k的组合，之后在把所有k组合存进ans中
	}
	return ans
}

动态规划 DP 算法

• 设定一个数组，存放到达第 n 层的跳法，假定只能从当前元素的左和下移动
  • 找一个位置，分析到达这个位置的前置条件，并将这些条件以二维数组的方式相加
  • 例如： a[i][j] = a[i-1][j] + a[i][j-1]
• 倒着分析，找关系
• 处理极值
  • arr[i][0] = 1
  • arr[0][j] = 1

// 生成一个二维数据的空数组
function Array2(m, n) {
	let _array = new Array(m)
	for (let i = 0; i < m; i++) {
		let emptyArr = new Array(n)
		for (let j = 0; j < n; j++) {
			emptyArr[j] = 0
		}
		_array2[i] = emptyArr
	}
	return _array2
}
function totalPath(m, n) {
	let arr = Array2(m, n)
	for (let i = 0; i < m; i++) {
		arr[i][0] = 1
	}
	for (let j = 0; j < n; j++) {
		arr[0][j] = 1
	}
	for (let i = 1; i < m; i++) {
		for (let j = 1; j < n; j++) {
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
		}
	}
	return arr[m - 1][n - 1]
}