【第十六天 - 动态规划 介绍】

Q1. 动态规划(Dynamic Programming)是什麽 ?

• Dynamic programming，简称DP，是一种多阶段决策出最佳解的方法，他会将问题分成子问题、子子问题...，拆成多个子问题进行求解，并且求出最佳解

• DP 可以大致理解为是分治法 + 记忆法

  • 首先定义出将大问题切割为子问题的方法。
  • 当一个子问题的答案被计算出来後，采取记忆法，将答案储存在记忆体中，避免未来重复计算。

• 以计算费氏数列为例：
  

• 计算 f(5)：
  

• 可以看到图中绿色的数字都会重复计算，而随着 n 越大，重复计算的会越多。

• 此时可以将计算过的答案保存在记忆体中，用空间换取时间，大幅节省效能。

参考资料：https://www.gushiciku.cn/pl/pKW7/zh-tw

参考资料：https://codertw.com/程序语言/586675/

Q2. 学会 动态规划概念可以做什麽 ?

• 动态规划问题在程序竞技比赛中，是经典的问题，常见的问题有：
  • 背包问题
  • 最佳二分搜寻树
  • 切割钢条问题
    
    参考资料：https://zhuanlan.zhihu.com/p/368171848

Lab. 明天要解的题目：53. Maximum Subarray

• 题目叙述：https://leetcode.com/problems/maximum-subarray/

• 题目叙述：

  • 题目会给一个 nums 的 list，需要找出至少一个数字的连续值，他们相加的结果会是最大的

  

• 测资的 Input/Output

  • 会给一个 nums 的 list，需要回传连续相加最大的值
    

• 题目的条件

  • list 长度在 1~30000 间
  • 每个值借於 -100000 ~ 100000 间
    

• 看完题目，你要思考：

  • 你是否把每个 list 值相加结果储存起来?
  • 你是否能不使用额外使用 list 空间解决这一题?
  • 什麽算法可以不造成超时?