动态规划

【自顶向下】从一个规模较大的问题 f(20),向下逐渐分解规模,直到 f(1)f(2)触底,再逐层返回答案,这就是【自顶向下】

【自顶向上】直接从最低下,最简单,问题规模最小的f(1)f(2)开始往上推,直到推到想要的答案f(20),这就是动态规划的思路。


求解动态规划的核⼼问题是穷举。

  • 但是这类存在重叠子问题,直接暴力搜索效率较低。故需要一个备忘录或者DP Table,避免不必要的计算。

  • 其一定具备最优子结构,才能通过子问题的最值得到原问题的最值。

  • 由于问题千变万化,穷举所有可行解不不容易,故需要列出正确的状态转移方法

重叠子问题,最优子结构,状态转移方程是动态规划的三要素。

写出状态转移方程一般是最难的,一个辅助框架:

明确 状态 -> 定义 dp数组/函数的含义 -> 明确 选择 -> 明确 base case。

摘自算法小抄

阅读更多

剑指offer-47

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

阅读更多

剑指offer-46

剑指 Offer 46. 把数字翻译成字符串

给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

阅读更多

leetcode-96

96. 不同的二叉搜索树

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

阅读更多