牛客经典必刷编程题库
CC224 最大字母矩阵给定一个string数组dic，代表单词列表，同时给定列表的长度n，请返回最大子矩阵的面积，其中子矩阵中的行和列相同，且有相同字母组成。保证单词的大小小于等于50，且某一长度的串的数量小于等于12。
测试样例：
12["aaa","aaa","aaa","bb","bb"]返回：9
刚开始以为是一个字符一个元素，然后找相同字符的最大矩阵，且行要等于列，采用动态规划的思路，代码如下：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.util.*;// class AlphaMatrix {public class AlphaMatrix { public int findAlphaMatrix(String[] dic, int n) { // write code he ...
algorithm
动态规划
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 知乎 (zhihu.com)
最少钞票数量问题引入
假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。
这里使用贪心算法：首先使用最大面值，直到剩余的金额不满最大面值则依次向下，直到满足w。
但如果面额为1， 5， 11的面额纸币凑15时，贪心算法会得到错误的结果：
11+1+1+1+1 5张，但实际上完全可以 5+5+5 3张
而贪心算法只能考虑眼前利益
那考虑其他办法，比如使用暴力算法，但这样的情况过多，时间无法承受。
重新分析：当我们第一步选用11元面值时，会面对w=4的情况:从上图= f(4)+1.同理,当我们第一步选用1,w=14:cost=f(14)+1,第一步选用5,w=10:cost = f(10)+1.
其中,cost为钞票数量,f为最少钞票数,那此时f(15) = min(以上三种cost情况)
这就是动态规划
...