对于一个字符串，对字符串进行分割，分割后的每个子字符串都为回文串，求解所有可行的方案
这个问题可以使用贪心算法与动态规划来求解
步骤如下：
（1）先得出所有的单个字符的回文串，单个字符必定是回文串, 若substr = string[i:j+1]且为回文串，则记为p[i][j] = True
（2）若p[i][j]=True且str[i-1]=str[j+1], 则p[i-1][j+1]也为回文串
思考：给定一些1元，2元，5元的纸币，问至少需要多少张，才能达到总价值为N
题目：给定一个长度为N的数组，找出最长递增子序列；例如：给定一个长度为6的数组A{5, 6, 7, 1, 2, 8}, 则其最长的单调递增子序列为{5, 6, 7, 8}, 长度为4
求解最长单调递增子序列的长度如下：
求解最长单调递增子序列本身：
代码实现（使用python实现如下）
#!/usr/bin/env python#! _*_ coding:UTF-8 _*_def lis(): global data # longest[i]表示以data[i]结尾的最长单增子序列的长度 global longest # 求解的结果， 最长单增子序列的长度 global nlis global prefix global result size = len(data) #首先对longest进行初始化 for i in range(size): longest.append(1) #遍历生成中间结果 for i in range(1, size, 1): for j in range(i): if data[j] <= data[i]: longest[i] = max(longest[i], longest[j] + 1) nlis = max(nlis, longest[i])if __name__ == "__main__": data = [1, 4, 5, 6, 2, 3, 8, 9, 10, 11, 12, 12, 1] longest = [] nlis = 0 prefix = [] result = [] lis() print longest
结果：
/Users/liudaoqiang/PycharmProjects/numpy/venv/bin/python /Users/liudaoqiang/Project/python_project/bat_day16/lis_test.py[1, 2, 3, 4, 2, 3, 5, 6, 7, 8, 9, 10, 2]Process finished with exit code 0
