动态规划

动态规划是一种常见的算法思想，常用于解决最优化问题。动态规划通常是用递推的方式解决问题，其中一个子问题的解可能会被多次使用。

常见的动态规划问题包括：

• 最长公共子序列问题：给定两个字符串，求它们的最长公共子序列。
• 0-1背包问题：给定一组物品，每个物品有一个重量和一个价值，同时给定一个背包容量，求在不超过背包容量的情况下，能够获得的最大价值。
• 最长递增子序列问题：给定一个序列，找到其中最长的递增子序列。
• 编辑距离问题：给定两个字符串，通过删除、插入或替换字符的方式，将一个字符串转换成另一个字符串，求最少需要多少次操作。
• 股票买卖问题：给定一个数组，表示每天的股票价格，可以进行多次交易，但必须在买入新股票之前卖出手中的股票，求最大收益。
• 最大子矩阵问题：给定一个矩阵，找到其中最大的全1子矩阵。
• 最大子序列和问题：给定一个整数数组，找到其中最大的连续子序列的和。
• 最长回文子序列问题：给定一个字符串，找到其中最长的回文子序列。
• 分割回文串问题：给定一个字符串，将它分割成若干个回文子串，求最少需要分割多少次。
• 最小路径和问题：给定一个m*n的矩阵，从左上角出发，每次只能向下或向右移动一格，到达右下角的最小路径和是多少。