算法-动态规划

鹿酒 2022/3/1 算法

动态规划的入门难度题目

动态规划是把多级决策的过程拆分成一级级的字问题的最优解，最直观的代码表示就是递归。

什么情况下可以使用动态规划：任何最短路的子路径相对于子问题始、终点最短

# 上楼的方法

问：假设有楼梯有n级，每次上1级或者2级，请问有多少种上楼的方法？

思路：倒推如下，最后一次到n，那么倒数第二次到n-1或者n-2；那么到了3级时，再前一次是在1 / 2，如果到2，上一级定是1，所以用递归可以得到结果

function upstairs(n){
  if(n === 1 || n === 2)return n // 边界判断
  if(n === 3) return (n - 1) + (n - 2) // 边界判断
  return upstairs(n - 1) + upstairs(n - 2)
}
// [upstairs(1),upstairs(2),upstairs(3),upstairs(4),upstairs(5),upstairs(6)]  => [1, 2, 3, 5, 8, 13]

1
2
3
4
5
6

但是由于递归过于占用内存，当n值较大时，页面就卡死了，我在自己的笔记本上尝试，n大于32的时候就开始卡得不成样子了，所以代码需要优化下。

因为上面递归的语法十分像斐波那契数列，所以我就按照这个思路整理代码如下，

function upstairs_1(n){
  var arr = [1, 2, 3]
  for (let i = 3; i < n; i++) {
    arr[i] = arr[i-2] + arr[i-1]
  }
  return arr[n-1]
}
// upstairs_1(100) => 573147844013817200000
// upstairs_1(2000) => Infinity

1
2
3
4
5
6
7
8
9

这下内存久不会溢出了。

# 不同路径

问：在n*m二维网格中，从(0,0)点移动到(n,m)点最多有多少种移动方法？条件：只能向右、向下移动，一次只能移动一格。

思路：倒推可得，(n,m)的上一点一定是(n-1,m)或(n,m-1)，当n或者m等于1时，需要忽略，所以f(0, n)、f(m, 0)的结果一定为1

function uniquePaths(m, n){
  // 生成一个m行n列 由0填充的二维数组
  var arr = new Array(m).fill(0).map(e=>new Array(n).fill(0))
  // 根据已知条件可知第一行、第一列都应该由1填充（走到这些点点可能性都只有一种）
  for (let i = 0; i < n; i++) {
    arr[0][i] = 1
  }
  for (let i = 0; i < m; i++) {
    arr[i][0] = 1
  }
  // 根据f(n,m) = f(n-1,m) + f(n, m-1) 填充余下位
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      arr[i][j] = arr[i-1][j] + arr[i][j-1]
    } 
  }
  return arr[m - 1][n - 1]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这种思路虽然可以解决问题，但是由于循环嵌套循环（空间复杂度O(m*n)），在数字稍大的情况下还是会出现内存溢出的

另一种思路：从左上到又下一共会移动(n-1)+(m-1)步，因此总的路径数等于从m+n-2次移动中选择m-1次向下移动的次数，即

$$ C^{m-1}_{m+n-2} = {(m+n-2)(m+n-3)...m \over (m-1)!} = {(m+n-2)! \over (m-1)!(n-1)!} $$

function uniquePaths_1(m, n){
  function jiecheng(x){ // 先实现阶乘
    var arr = []
    for (let i = 1; i <= x; i++) {
      arr.push(i)
    }
    return arr.reduce((sum, e)=>sum*e)
  }
  // 再按照公式导出结果计算
  return jiecheng(m+n-2) / (jiecheng(m-1) * jiecheng(n-1))
}
function uniquePaths_2(m, n){
  // 再次优化代码
  let num = 1
  for (let x = n, y = 1; y < m; ++x, ++y) {
    num = Math.floor(num * x / y)        
  }
  return num
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 最大子数组和

问：现有任意数组，求数组中最大的子数组的和

思路：（贪心算法）当前指针所指的元素之前的项的和小于0 丢弃前面的重新累积

function maxChildArrSum(array){
  var sum = 0, // 指最后的最大和
      _sum = 0; // 指 当前的 和
  array.forEach(e=>{
    _sum += e
    if(_sum < 0){
      _sum = 0
    }
    sum = Math.max(sum, _sum)
  })
  return sum
}

1
2
3
4
5
6
7
8
9
10
11
12

思路：（动态规划）当前指针所指的元素的上一个元素如果大于0 累加

function maxChildArrSum1(array){
  var sum = array[0], // 指最后的最大和
      prev = 0; // 指 前一个元素累计数
  array.forEach(e=>{
    prev = Math.max(prev + e, e) // 如果e大于0，那么给元素叠加起来
    sum = Math.max(prev, sum) // 如果累计值大于sum就更新sum
  })
  return sum
}

1
2
3
4
5
6
7
8
9

鹿酒的博客