动态规划(1)

什么动态规划

动态规划是一种解决棘手问题的方法，它将问题分成小问题，并着手先解决这些小问题

动态规划的使用场景

• 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。