什么动态规划
动态规划是一种解决棘手问题的方法，它将问题分成小问题，并着手先解决这些小问题
动态规划的使用场景
- git diff
- DNA链的相似性
- 字符串相似程度
- word断字能力
背包问题
小偷有一个容量4kg的背包，请问偷什么价值最大？
| 物品 | 价值 | 重量 |
|---|---|---|
| 吉他 | ￥1500 | 1kg |
| 音响 | ￥3000 | 4kg |
| 笔记本 | ￥2000 | 2kg |
| 物品 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 吉他 | G1000 | G100 | G1000 | G1000 |
| 音响 | G1000 | G1000 | G1000 | Y3000 |
| 笔记本 | G1000 | B2000 | BG3500 | BG3500 |
计算公式
上一个单元格的值与当前商品价值+剩余空间价值中比较大的那个
引申
如果顺序打乱会影响结果么？
如果再加一个手机价值￥2000，重1kg，需要重新规划么？
如果出现了一个钻石价值￥50000，重0.5kg，需要重新规划么？
可以偷商品的一部分么？
如果相互依赖可以用动态规划解决么？
最大正方形
题目描述
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
思路
开动小脑袋想一想
image
https://leetcode-cn.com/progress/
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
