算法与数据操作--动态规划与贪婪算法

动态规划

写在前面：本文主要记录一些学习时候的理解和自己重写代码时犯的一些错误，备查看；主要参考的是《剑指offer》与《学习javascript数据结构与算法》

可以用动态规划算法求解问题的几个特点：

• 是一个求最优解的问题

• 整体问题的最优解依赖于各个子问题的最优解

• 把问题分解成若干小问题后，这些小问题有相互重叠的更小子问题（p95有一个剪绳子例子的解释，有些局限，待解决多个动态规划问题后再对此点写一些自己的理解）

• 从上往下分析问题，从下往上解决问题。从解决小问题开始，将小问题的最优解存储下来，再把这些子问题的最优解组合起来解决大的问题

  剪绳子问题：长度为n的绳子，剪成m段（m,n都为整数，m>1,n>1）,求这些绳子长度乘积的最大值
  function maxProductAfterCutting_solution1(length) {
  if (length <= 1) return 0;
  if (length === 2) return 1;
  if (length === 3) return 2;      //1
  
  let result = [0, 1, 2, 3];
  
  for (let i = 4; i <= length; i++) {
    let max = 0;
    for (let j = 1; j <= i / 2; j++) { // 2
      let temp = j * result[i - j];    // 3
      if (temp > max) max = temp;
    }
    result[i] = max;
  }
  return result[length];
  }

  在自己复现代码时，有三处理解的不深刻，导致了一些问题，在调试后更正过来。有了以下几点新理解：

• 注释1处：之前认为长度为3不用进行特殊处理，大循环从3开始，这样导致的问题就是推入数组中的result [3]为2，虽然结果没错，但放在result 中就有问题，在i=4时，会用到result [3]，其实想要的结果应该是3本身，但取得的却是2，这与大一些的数取f(n-i)最优值不同，4以上的最优解经过循环后都大于等于数字本身，从result取的值没有问题，3不行，3本身的最优解为2，故应单独处理；

• 上述这一种编程的思路可以看出，result数组中存放的并不全是最优解，从第4个起才是，数字4之前都进行了单独的处理，不要被某些惯性思维所局限，比如这题中，认为result 中就是存放的所有问题的最优解，没有必要花时间处理这个，不合要求的单独处理即可。

• 注释2、3两处在第一次写时，将现在的i写成了length ，说明当时对动态规划的思想没理解到位。程序中，小循环是针对每个子问题的求解，从下至上求解子问题的最优解，内部不应该有length这样的整体问题的变量，自然结果也就稀奇古怪。