3.1概述

  1. 核心思想： 
  2.     动态规划是计算机中解决最优化问题的一种方法
  3.     通过避免重复节点的计算来提高计算速度
  4.     使用字典或者哈希表保存计算中间结果，因此也称之为【记忆化搜索】
  5.     这也是动态算法是一种用空间换时间的策略
  9. 经典案例：
  10.     给定一个无序数组，找出其中最长的、递增的子序列的长度
  11.         思路：
  13.             暴力搜索：
  14.                 定义一个函数 L(arrs,i), 返回从数组第i个长度开始的最长序列的长度
  15.                 具体如下：
  16.                     public int L(int[] arrs, int i) {
  17.                         for(int j=i+1;j<arrs.length;j++) {
  18.                             if(arrs[j]>arrs[i]) {
  19.                                 return L(j) + 1;
  20.                             }                            
  21.                         }
  22.                     }
  23.                 遍历数组，找最长的递增子序列长度
  24.                     public int R(int[] arrs) {
  25.                         int max_length = 1;
  26.                         for(int i = 0; i<arr.length; i++) {
  27.                             max_length = max(max_length, L(arrs, i))
  28.                         }
  29.                         return 
  30.                     }
  34.     给定一个无序数组，找出其中连续子序列的最大和
  36. 动态规划算法的一般思路：
  38.     穷举法/暴力搜索
  39.     如果发现大量重复计算
  40.     就用哈希表将中间计算结果保存下来
  41.     之后遍历到相同节点，直接从哈希表取值