动态规划

• 回顾
  • 递归 +分治 +回溯 + 动态规划
  • 找到最近的最简的解决方法，将其拆解成可重复解决的问题
• 递归代码模板 ：Recursion

public void recur(int level, int param) {
    // terminator    递归终止条件
    if (level > MAX_LEVEL) {
        // process result
        return;
    }
    
    // process current logic 处理当前逻辑
    process (level, param);
    
    // drill down		下探到下一层
    recur (level : level + 1, newParam);
    
    // restore current status  恢复当前层状态 
    // 如果改变的状态都是在参数上面的，因为递归调用的时候参数是会被复制的，如果是简单变量，就不需要恢复
}

• 分治：Divide & Conquer

  • 递归状态树
  • 分治代码模板

  private static int divide_conquer(Problem problem) {
      if (problem == NULL) {
          int res = process_last_result();
          return res;
      }
      
      subProblems = split_problem(problem);
      
      res0 = divide_conquer(subProblems[0]);
      res1 = divide_conquer(subProblems[1]);
      
      result = process_result(res0, res1);
      
      return result;
  }
  

感触

1. 人肉递归低效
2. 找到最近最简方法，将其拆解成可重复解决的问题
3. 数学归纳法思维（抵制人肉递归的诱惑）

本质：寻找重复性--> 计算机指令集

如果递归不熟，记得画 递归树

eg：斐波那契数列

节点的扩散是指数级的，状态是指数个

动态规划 Dynamic Programming

1. Wiki 定义

   Programming 这里可以理解成递推，推导，所以就是动态推导

   “Simplifying a complicated problem by breaking it down into simpler sub-problems”

   (in a recursive manner)

   本质上就是 递归 + 分治 问题，多了一个最优子结构

2. Divide & Conquer + Optimal substructure

   分治 + 最优子结构

一般动态规划的问题都是这样的

• 求最优解
• 或者求最大值
• 或者求最少的方式

正因为有最优子结构，所以不需要在每一步将所有状态都保存下来，只需要存最优状态，当然还需要证明：如果每一步存的都是最优的值，最后就能推导出一个全局最优的值

因此：引入两个内容：

• 缓存，或者说状态的存储数组
• 在每一步把次优的状态淘汰掉，只保留在这一步里面最优的或者是较优的一些状态来推导出全局最优

关键点

动态规划 和 递归 或者 分治 没有根本上的区别（关键看有无最优的子结构）（如果没有最优子结构说明要把所有子问题计算一遍，同时最后把子问题合并到一起）

共性：找到重复子问题（为什么？因为计算机指令只会 if else 和 loop）

差异性：最优子结构、中途可以 淘汰 次优解

如果不进行淘汰，也就是傻递归或者傻分治，通常是指数级的时间复杂度，可以参考斐波那契数列

淘汰次优解通常可以降到 O(n^2) 或者 O(n) 的时间复杂度

实战例题

1. Fibonacci 数列、路径计数

fib(n) = fib(n - 1) + fib(n - 2)

fib(0) = 0

fib(1) = 1

傻递归

int fib(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

• 简化

  1. 可以写得更简洁一点

     用三元表达式，但是不改变时间复杂度

     int fib(int n) {
         return n <= 1 ? n : fib(n - 1) + fib(n - 2);
     }
     

  2. 加缓存，记忆化搜索

     int fib(int n, int[] memo) {
         if (n <= 0) {
             return 0;
         } else if (n == 1) {
             return 1;
         } else if (memo[n] == 0) {
             memo[n] = fib (n - 1) + fib (n - 2); 
         }
         return memo[n];
     }
     

  3. 继续优化上述代码

int fib(int n, int[] memo) {
    if (n <= 1) {
        return n;
    }
    
    if (memo[n] == 0) {
        memo[n] = fib (n - 1) + fib (n - 2);
    }
    return memo[n];
}

时间复杂度变为 O(n)

Bottom UP

与其用递归，不如写一个循环

• F[n] = F[n - 1] +F[n - 2]

• a[n] = 0, a[1] = 1;

  for (int i = 2; i <= n; ++i) {

  ? a[i] = a[i - 1] + a[i - 2];

• a[n]

• 0, 1, 1, 2, 3, 5, 8, 13, ...

• 这就是自底向上

• 递归是 从问题（fib(6）向下一步一步到叶子节点(fib(1)) ，这种方法称为 自顶向下，

  • 6 --> 5 和 4
  • 5 --> 4 和 3
  • 4 --> 3 和 2 ...

• 计算机思维是 初始值已经有了，0 和 1，然后 相加 1，然后 1， 1 相加 2，1,2 相加 3 ，...

  这是自底向上

• 对于熟练的选手，竞赛型选手全部都是自底向上 写循环开始进行递推了

• 熟练的话要 自底向上

2. 路径计数 Count the paths

前面的是 一维数组进行动态递推，而且没有取舍

复杂的 DP

1. 维度的变化，二维空间或者三维的
2. 取舍最优子结构

• 题目

  从左上角走到右下角，只能向下或者向右走一步不能往左或者上走，黄色点表示障碍物，不能走，问有多少种不同路径？

• 分析
  

? paths (start, end) =

? paths (A, end) + paths (B, end)

paths (D, end) + paths (C, end) paths (C, end) + paths (E, end)

是不是有点像 Fibonacci 数列

int countPaths (boolean[][] grid, int row, int col) {
    if (!validSquare(grid, row, col)) return 0;
    if (isAtEnd(grid, row, col)) return 1;
    return countPaths(grid, row - 1, col) + countPaths(grid, row, col - 1);
}

• 怎么变成 递推 呢

  自底向上

求 A 和 B 有多少种走法是不知道的，但是 从 end 向上我们是知道 两个格子都只有 1 种走法，同时，最下面一行和最右边一列都是只有一种走法的，也就是 从 end 往左和往上推反而是更好推一点

如果是障碍物，则走法为0；如果不是障碍物，则走法为 右边格子走法 + 下边格子走法

接下来得到了递推公式

Fibonacci 的递推公式很简单，就是 F(n) = F(n - 1) + F(n - 2)

• 状态转移方程 （DP 方程）

  opt 就是 optimal 最优的

  opt[i, j] = opt[i + 1, j] + opt[i, j + 1]
  

  完整逻辑

  if a[i,j] = '空地' ：		// 这里看是否是空地就是筛选的过程
  	opt[i, j] = opt[i + 1, j] + opt[i, j + 1]	// 有时候会变成最小值或者最大值
  else :
  	opt[i, j] = 0
  

这样可以写完

动态规划关键点

1. 最优子结构 opt[n] = best_of (opt[n - 1], opt[n - 2], ...)

2. 储存中间状态：opt[n]

3. 递推公式（状态转移方程或者 DP 方程）

? Fib : opt[n] = opt[n - 1] + opt[n - 2]

? 二维路径：opt[i, j] = opt[i + 1, j] + opt[i, j + 1] (且判断 a[i, j] 是否是空地)

养成走这三步的习惯，初学者来说最重要的是 第二步

路径计数的完整代码

[LeetCode 62. 不同路径]https://leetcode-cn.com/problems/unique-paths/

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

实战例题3：最长公共子序列

最长公共子序列 longest common subsequence LCS

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示:

• 1 <= text1.length <= 1000

• 1 <= text2.length <= 1000

• 输入的字符串只含有小写英文字符。

• 解析：

字符串问题

1. S1 = ""

   S2 = 任意字符串

2. S1 = "A"

   S2 = 任意

3. S1 = ".......A"

   S2 = ".....A"

   这种情况的最长子序列最少为1，也就是 A 和 A

   然后可以转换成子问题，求S1前面的子序列和 S2 前面的子序列的最长公共子序列的值 再 加1

eg：ABAZDC 和 BACBAD

最后得到的 4 这个值就是 C 到 最前面的子串以及 D 到最前面的子串的 最长公共子序列，也就是 text1 和 text2 的最长公共子序列

再比如

3 这个格子是 ABAZDC 和 BAC 之间的最长公共子序列，它最后一个字符是一样的，就转换成求

AB 这个子序列和 DZABA 这两个子序列的 最长公共子序列 再加1，它们的 最长公共子序列 就是 2,2 + 1 = 3

子问题

状态方程

• S1 = "ABAZDC"

  S2 = "BACBAD"

•   if S1[-1] != S2[-1]: LCS[s1, s2] = Max(LCS[s1 - 1, s2], LCS[s1, s2 - 1])
    LCS[s1, s2] = Max(LCS[s1 - 1, s2], LCS[s1, s2 - 1], LCS[s1 - 1, s2 - 1])
  

  具体逻辑的话是下面的一行，但是可以证明，下面的等于上面的

  因为在计算 LCS[s1 - 1, s2] 和 LCS[s1, s2 - 1] 的时候已经包括了 LCS[s1 - 1, s2 - 1] 的情况

  这里用 Python ， s1[-1] 表示 s1 的最后一个字符，Java 的形式就是 s1[s1.length - 1]

•   if S1[-1] == S2[-1]: LCS[s1, s2] = LCS[s1 - 1, s2 - 1] + 1
    LCS[s1, s2] = Max(LCS[s1 - 1, s2], LCS[s1, s2 - 1], LCS[s1 - 1, s2 - 1], LCS[s1 - 1, s2 - 1] + 1)
  

  同样，可以证明，下面 = 上面

DP 方程

简化下来就是

if S1[-1] != S2[-1]: LCS[s1, s2] = Max(LCS[s1 - 1, s2], LCS[s1, s2 - 1])
if S1[-1] == S2[-1]: LCS[s1, s2] = LCS[s1 - 1, s2 - 1] + 1

思维的关键

两个字符串的问题可以认为是编辑距离的问题，转换成二维数组的递推问题

也就是 如何把一个动态规划的问题，定义出它的状态

public int longestCommonSubsequence(String text1, String text2) {
    char[] s1 = text1.toCharArray();
    char[] s2 = text2.toCharArray();
    int[][] dp = new int[s1.length + 1][s2.length + 1];
    
    for (int i = 1; i < s1.length + 1; i++) {
        for (int j = 1; j < s2.length + 1; j++) {
            // 如果末端相同
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                /*
                	注意这里可能会难理解为什么是 s1[i - 1] == s2[j - 1]
                	是为了方便第一个值取 s1[0] 和 s2[0]
                	而 dp[][] 数组的 dp[0][0] 在这里是没用的，开始就是 dp[1][1] 一直到
                	dp[m][n]，dp[m][0] 和 dp[0][n] 在这里都是为了 方便 i - 1 可以取到 0
                	因为状态方程里面必须有 i - 1
                 */
            } else {
                // 末端不同
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[s1.length][s2.length];
}

也可以这样写

public int LCS(String s1, String s2) {
    int m = s1.length() + 1;
    int n = s2.length() + 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[m][n];
}

这种解法的时间和空间复杂度都是 O(m*n)

[空间优化]https://leetcode.com/problems/longest-common-subsequence/discuss/351689/JavaPython-3-Two-DP-codes-of-O(mn)-and-O(min(m-n))-spaces-w-picture-and-analysis

看不懂

动态规划小结

1. 打破自己的思维惯性，形成机器思维

   因为机器只会重复性

2. 理解复杂逻辑的关键

3. 也是职业进阶的要点要领

补充内容

B站搜索：mit 动态规划

5 “easy” step to DP：

1. define subproblems

2. guess (part of solution)

3. relate subproblem solutions

4. recurse & memorize

   or build DP table bottom-up

5. solve original problem

也就是

1. 分治，找重复性和子问题

2. 定义出状态空间，可以用记忆化搜索递归，或者是自底向上进行推导

实战题目

1. 爬楼梯问题

需要 n 阶你才能到达楼顶

每次可以爬 1 或 2 个台阶，有多少种不同的方法可以爬到楼顶

• 分析：

• 比如 10 级 台阶，只考虑最后一步的话，只有两种方法，就是从 9 爬 1级 和 从 8 爬两级

  所以 climbingStairs(10) = climbingStairs(9) + climbingStairs(8)

  也就是斐波那契数列 1,1,2,3

  DP 方程 F(n) = F(n -1) + F(n - 2)

  递归的话

public int climbingStairs(int n) {
    if (n <=1) return 1;
    return climbingStairs(n - 1) + climbingStairs(n - 2);
}

DP 的话

public int climbingStairs(int n) {
    int[] res = new int[n];
    res[0] = 1;
    res[1] = 1;
    for (int i = 2; i <= n; i++) {
        res[i] = res[i - 1] + res[i - 2]; 
    }
    return res[n];
}

上面代码是有错误的，发现了吗？

出现了数组越界异常，第一行中定义的 res[] 长度是 n 的，所以索引中不会有n，应该定义成 n + 1

下面是正确的代码

public int climbingStairs(int n) {
    int[] res = new int[n+1];
    res[0] = 1;
    res[1] = 1;
    for (int i = 2; i <= n; i++) {
        res[i] = res[i - 1] + res[i - 2]; 
    }
    return res[n];
}

这里发散思维一下

• 1. 假设 每次可以上1级，2级，3级台阶的话怎么弄，递推方程应该怎么写

     DP：F(n) = F(n - 1) + F(n - 2) + F(n - 3)

     public int climbStairs2(int n){
             int[] res = new int[n + 1];
             res[0] = 1;
             res[1] = 1;
             res[2] = 2;
             for (int i = 3; i <= n; i++) {
                 res[i] = res[i - 1] + res[i - 2] + res[i - 3];
             }
             return res[n];
     }
     

     2. 假设 每次可以上1级，2级，3级台阶，且相邻两步的步伐不能相同，递推方程应该怎么写 

        dp[i][1] = dp[i - 1][2] + dp[i - 1][3];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][3];
        dp[i][3] = dp[i - 3][1] + dp[i - 3][2];
        

        public int climbStairs(int n) {
            int[][] dp = new int[n][3];
            
            dp[0] = new int[] {1,0,0};		// 此处表示的是第一级台阶的方法
            dp[1] = new int[] {0,1,0};		// 此处表示的是第二级台阶的方法
            dp[2] = new int[] {1,1,1};		// 此处表示的是第三级台阶的方法
            
            for (int i = 3; i < n; i++) {	// 从第 4 级台阶开始可以递推计算
                dp[i][0] = dp[i - 1][1] + dp[i - 1][2];
                dp[i][1] = dp[i - 2][0] + dp[i - 2][2];
                dp[i][2] = dp[i - 3][1] + dp[i - 3][0];
            }
            
            return dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2];
        }
        

2. 三角形最小路径和

LeetCode 120

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分

• 解析：

1. brute-force 暴力法

   类似 左括号右括号问题，或者 coin-change 问题，或者爬楼梯问题

   递归， n层递归，每一层可以 left 或者 right

   时间复杂度 2^n

2. DP

   1. 找重复性（分治）

           [2],
          [3,4],
         [6,5,7],
        [4,1,8,3]
      

      2 到下面可以分解成 3 到下面的解和 4 到下面的解 两者间的最小值，因为 2 只能走到 3 或者 4

      假设 横坐标为 i，纵坐标为 j

      problem(i, j) = min(sub(i + 1, j), sub(i + 1, j + 1)) + a[i, j]

   2. 定义状态数组

      OPT 是一维的还是二维的，状态值要定义好

      f[i, j] 表示 从 点 (i, j) 到底边的最小路径和

   3. DP 方程列出来

      f[i, j] = min(f[i + 1, j] + f[i + 1, j + 1]) + a[i, j]

   时间复杂度 O(n^2)

   空间复杂度 O(n^2)

Java 代码

class Solution {
    public int minimumTotal(List> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n + 1][n + 1];		// 注意这里数组要定义成 (n+1) * (n+1) 的
        
        for (int i = n - 1; i >= 0; i--) {		// 注意 i = n-1 是最后一行，因为是从 0~ n-1 的
            for (int j = 0; j <= i; j++) {		// 判断条件 j<=i 是因为 第 i 行只有 i 个元素
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);		
                // 这里体现出了为什么 dp 要定义成 n+1 的，最后一行的时候需要 dp[n][i] = 0
            }
        }
        return dp[0][0];
    }
}

Python 代码

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        dp = triangle                   # 一开始就把 triangle 的值赋到 dp 里面
        # 所以 dp 初始化不是 0 的二维数组
        # 好处：dp 方程不需要加 i，j 了
        # 这里自底向上进行循环
        for i in range(len(triangle) - 2, -1, -1):  # 从 倒数第二行开始，因为 4,1,8,3 是 倒数第一行，不用，然后每次向上进行循环
            for j in range(len(triangle[i]))：
            	dp[i][j] += min(dp[i + 1][j], dp[i + 1][j + 1]) # 这里 += 是因为 一开始 dp[i][j] 就被初始化过了 triangle[i][j] 的值
                
        print(triangle[0][0])
        return dp[0][0]			# 也就是最上面的一行        

C++ 代码

class Solution {
    public:
    int mnimumTotal(vector > &triangle) {
        for (int i=triangle.size()-2; i>=0; --i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};
// 这样的代码在工业里面是不行的，因为直接把 triangle 改的物是人非了

空间优化

实际递推中，计算 dp[i][j] 时，只用到了下一行的 dp[i+1][j] 和 dp[i+1][j+1]

因此 dp 数组不用定义 n 行，只要定义 1 行就够了

将 i 所在的维度去掉，优化空间

class Solution {
    public int minimumTotal(List> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
                // 每向上递推一行，就把之前的覆盖掉，因此只用了一维的数组
            }
        }
        return dp[0];
    }
}

时间复杂度：O(n^2)

空间复杂度：O(n)

递归（自顶向下）

模板

1. terminator 递归终止条件

   这里就是 到最后一行

2. process 处理当前逻辑

   这里就是 分成子问题，求较小者然后加上自身

3. drill down

class Solution {
    int row;
    
    public int minimumTotal(List> triangle) {
        row = triangle.size();
        return helper(triangle, 0, 0);
    }
    
    private int helper(List> triangle, int i, int j) {
        if (i = row - 1) {			// row 是 triangle.size()，也就是到了最后一行
            return triangle.get(i).get(j);
        }
        int left = helper(triangle, i + 1, j);
        int right = helper(triangle, i + 1, j + 1);
        return Math.min(left, right) + triangle.get(i).get(j);
    }
}

自顶向下的方法，这个方法是超时的

时间复杂度 O(2^n)

改进，避免重复计算

自顶向下，记忆化搜索

class Solution {
    int row;
    Integer[][] memo;
    
    public int minimumTotal(List> triangle) {
        row = triangle.size();
        memo = new Integer[row][row];
        return helper(triangle, 0, 0);
        
    }
    
    public int helper(List> triangle, int i, int j) {
        if (memo[i][j] != null)
            return memo[i][j]; // 这里是存储已经计算了的结果的关键，如果不为空说明计算过了，直接返回
        
        if (i == row - 1) {
            return memo[i][j] = triangle.get(i).get(j);
        }
        
        memo[i][j] = Math.min(helper(triangle, i + 1, j), helper(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
        
        return memo[i][j];
    }
}

3. 最大子序列和 

这道题难理解

LeetCode 53

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

• 解析：

• 状态方程很容易写出来

  dp[n] = Max(dp[n - 1] + a[n], a[n])

  但是有很多坑

  首先，这里的 dp 是 一定包含 a[n] 在内的最大连续子数组，而 a[n] 有可能是 负数，所以 dp[n] 并不是最终结果，还需要继续比较，设上一次的结果为 max，如果 max > dp[n]，则结果为 max，如果 max < dp[n] ，则结果为 dp[n]

• Java 代码

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int max = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
        	dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

• 空间优化

  为了节省空间，可以不开辟新的数组，

class Solution {
    public int maxSubArray(int[] nums) {
        int maxAns = nums[0];
        int sum = 0;		// 这里不用 dp[] 来存储
        for (int num: nums) {
            sum = Math.max(sum + num, num);
            maxAns = Math.max(maxAns, sum);
        }
        return maxAns;
    }
}

4. 延伸问题：乘积最大子序列

LeetCode 152

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

• 解析：

• DP：

    - 自底向上，保证 4 一定在，则分化为求 前三个数的乘积最大子序列，然后比较
    - dp[n] = max(dp[n - 1] * a[n], a[n])
    - 但是这里出现了问题，如果是两个负数，负负得正也可以
    - 所以这里的结论是：当前位置的最优解未必是由前一个位置的最优解转移得到的
  
    所以可以将 整的最大的结果存起来，也将 负的绝对值最大的结果也存起来，实际上就是 最小的值
  
    于是得到状态转移方程：
  
    `dp_max[n] = max( dp_max[n - 1] * a[n], dp_min(n - 1) * a[n], a[n] )`
  
    `dp_min[n] = min( dp_max[n - 1] * a[n], dp_min(n - 1) * a[n], a[n] )`
  

Java 代码

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] maxF = new int[n];
        int[] minF = new int[n];
        // 复制 maxF = nums, minF = nums
        System.arrayCopy(nums, 0, maxF, 0, n);
        System.arrayCopy(nums, 0, minF, 0, n);
        
        /* 
        	public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length) 
        	src:源数组；
			srcPos:源数组要复制的起始位置；
			dest:目的数组；
			destPos:目的数组放置的起始位置；
			length:复制的长度。
			注意：src and dest都必须是同类型或者可以进行转换类型的数组．
         */
        for (int i = 1; i < n; ++i) {
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(minF[i - 1] * nums[i], nums[i]));		// 注意 Math.max 没有直接比较三个数的
            minF[i] = Math.min(maxF[i - 1] * nums[i], Math.min(minF[i - 1] * nums[i], nums[i]));		// 其实到 n - 1 的时候，只要最大值就 ok 了，最小值没用了
        }
        
        int ans = maxF[0];
        for (int i = 1; i < n; ++i) {
            ans = Math.max(ans, maxF[i]);
        }
        return ans;
    }
}

渐进时间复杂度和渐进空间复杂度都是 O(n)

优化空间

由于 第 i 个状态只和第 i - 1 个状态有关，可以只用两个变量维护 i - 1 时刻的状态，一个维护 maxF，一个维护 minF

class Solution {
    public int maxProduct(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int mx = maxF, mn = minF;
            maxF = Math.max(mx * nums[i], Math.max(mn * nums[i], nums[i]);
			minF = Math.min(mx * nums[i], Math.min(mn * nums[i], nums[i]);
            ans = Math.max(maxF, ans);
        }
		return ans;
    }
}

程序一次循环遍历了 nums，渐进时间复杂度为 O(n)

空间复杂度为 O(1)，因为与 n 无关，只用了常数个临时变量

5. Coin Change 零钱兑换

LeetCode 322

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

解析：

如果问的是有多少种不同的组合方式，其实就是上楼梯问题

DP：自底向上

状态转移方程

F(n) = min(F(n - c[j])) + 1 其中 j 为 1 ~ n - 1

比如这里 F(11) = min( F(11 - 1), F(11 - 2), F(11 - 5)) + 1

• Java 代码

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];		
        Arrays.fill(dp, max);				
        /* 
        这里用 amount + 1 填充 dp[]，就是为了方便比较 dp[n] 和 amount
        看下面代码，dp 方程是在 coin < i 条件下才运转的，
        不满足条件则输出 -1，所以设置 dp[n] 初始值为 一个 大于 amount 的值，最后用三元输出
        */
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {	// 前提条件是 硬币的面额是小于当前要求的 n 的，否则返回-1
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

贪心 + DFS

1. 贪心

   1. 想用总硬币数最少，优先使用大额硬币，对 coins 从大到小排序
   2. 先用大硬币，再用回超过总额时，就可以递归下一层用稍小面值的硬币

2. 乘法对加法的加速

   1. 优先用大硬币进去尝试，可以用乘法算一下最多能丢几个

      k = amount / coins[c_index] 计算最大能投几个
      amount - k * coins[c_index] 减去扔了 k 个硬币后的值
      count + k 加 k 个硬币
      

   2. 如果丢多了无法凑出总额，再回溯减少大硬币数量

3. 最先找到的并不是最优解

   1. 注意不是现实中发行的硬币
   2. 考虑到有 [1, 7, 10] 这种情况，如果 14，10+1+1+1 会比 7 + 7先找到
   3. 还是要把所有情况都考虑完

4. ans 疯狂剪枝

   1. 快速算出一个贪心的 ans 之后，需要进行剪枝

5. 图解

• Java 代码

  class Solution {
      int res = Integer.MAX_VALUE;
      public int coinChange(int[] coins, int amount) {
          if (amount == 0) {
              return 0;
          }
          Arrays.sort(coins);
          minCoin(coins, amount, coins.length - 1, 0);
          return res == Integer.MAX_VALUE ? -1 : res;
      }
      
      private void mincion(int[] coins, int amount, int index, int count) {
          if (amount == 0) {
              res = Math.min(res, count);
              return;
          }
          if (index < 0) {
              return;
          }
          // 下标从 coins.length - 1 开始，是最大的 coin
          for (int i = amount/coins[index]; i >= 0 && i + count < res; i--) {
              /*
               	这里的 i + count < res 就是剪枝操作，非常关键
               	如果 i + count >= res，说明需要的币数比前面已经得到的最优解 res 还要多，
               	就不用循环了，所以这里要 i + count < res
               
               */
              // 用过面额最大的硬币后，amount 要减去 相应的数量
              mincoin(coins, amount - (i * coins[index]), index - 1, count + i);
          }
      }
  }
  

6. 打家劫舍

LeetCode 198

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 400

• 解析：

• 出了几次错误才写对。。。

• 首先容易分析状态方程为

  F(n) = Max(F(n - 2) + a[n], F(n - 3) + a[n - 1])

  举个例子，[100, 1, 1, 99, 2]

  从后向前看的话，2 和 99 两者是必选其一的，因为假设如果两个都不选，也就是 [100, 1, 1] 的 ans，是肯定可以加上 2 的；而如果加了 2 ，得到的结果是不一定 比可以加上 99 后的结果大的，所以就是上面的方程，然后要把 n < 3 的所有情况分析完，并且在前面的条件都加上，不加条件会数组越界异常

  以下是我经过多次修改后第一次通过的代码

  class Solution {
      public int rob(int[] nums) {
          int n = nums.length;
          int[] dp = new int[n];
          if (n == 0 || nums[0] == null) return 0;
          dp[0] = nums[0];
          if (n > 1) dp[1] = Math.max(nums[0], nums[1]);
          if (n > 2) dp[2] = Math.max((nums[0] + nums[2]), nums[1]);
          if (n > 3) {
              for (int i = 3; i < n; i++) {
                  dp[i] = Math.max((num[i] + dp[i - 2]), num[i - 1] + dp[i - 3]));
              }
          }
          return dp[n - 1];    
      }
  }
  

7. m大小的数组分割成 size-大小

[1, 2, 3], 2 --> {[1, 2], [1, 3], [2, 3]}
size 为 2

    // [1, 2, 3], 2        -->        {[1, 2], [1, 3], [2, 3]}  
    /**
     * 获取数组的 size-排列
     */
    public List getCombination(int[] arr, int size) {
        List result = null;
        return combination(arr, arr.length, size, new int[size], result);
    }


    public List combination(int[] arr, int arrLength, int size, int[] singleArr, List result) {
        if (size == 0) {
            int[] arrCopy = new int[singleArr.length];
            for (int j = 0; j < singleArr.length; j++) {
                arrCopy[j] = singleArr[j];
            }
            result.add(arrCopy);
            return result;
        }
        
        for (int i = arrLength; i >= size; --i) {
            singleArr[size - 1] = arr[i - 1];
            combination(arr, i - 1, size - 1, singleArr, result);
        }
        return result;
    }