终于学到这里了，一直觉得动态规划是一个很高档的东西hhhhh
动态规划是将大问题拆分成小问题，而小问题之间是相互关联的，且较为相似，因此可以将前面的计算结果记录下来用在后面的问题中，避免重复计算。DP有线性DP和非线性DP，线性DP将状态记录在数组上，而非线性DP则是将状态记录在树上的。
基础DP
最少硬币
从最小面额开始从前往后递推。
#include<limits.h>
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
unsigned int m[10005];
for(int i=0; i<=amount; i++){
m[i] = INT_MAX;
}
m[0]=0;
for(int i=0;i<coins.size();i++){
for(int j=coins[i];j<=amount;j++){
m[j]=min(m[j], m[j-coins[i]]+1);
}
}
if(m[amount]==INT_MAX){
return -1;
}
return m[amount];
}
};0/1背包
#pragma warning(disable:4996)
#include <bits/stdc++.h>
using namespace std;
#define MAX 101
int main() {
int TIME, NUM;
cin >> TIME >> NUM;
int dp[MAX][1001] = { 0 }; // 表示采m个草药需要消耗t时间
int time, value;
for (int i = 1; i <= NUM; i++) { // i为数量
scanf("%d", &time);
scanf("%d", &value);
for (int j = 0; j <= TIME; j++) { // j为耗时
if (j >= time) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time] + value);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
int max = 0;
for (int i = 1; i <= TIME; i++) {
if (dp[NUM][i] > max) {
max = dp[NUM][i];
}
}
cout << max;
}最开始我的状态转移是这么写的：
for (int j = 0; j <= TIME; j++) { // j为耗时
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time] + value);
}这样就丢失了一部分状态。
Tips
书上的小技巧：滚动数组，因为我们只需要通过上一行的数据来生成下一行的数据，所以实际上只需要一个一维数组，每一行从后往前递推覆盖。
这样做大大节省了空间。优化前：用时38ms，内存896.00KB；优化后：用时37ms，内存700.00KB。emmmm可能是数据量太小所以不明显，照理说空间占用会减小NUM倍。
for (int i = 1; i <= NUM; i++) { // i为数量
scanf("%d", &time);
scanf("%d", &value);
for (int j = TIME; j > 0; j--) { // j为耗时
if (j >= time) {
dp[j] = max(dp[j], dp[j - time] + value);
}
}
}最长公共子序列
https://leetcode-cn.com/problems/longest-common-subsequence/
靠自己写出了最优代码，太感人了，时间空间复杂度应该都很好了吧。
状态转移思路：设有字符串A和B，以及dp数组，dp[i]用于记录A中第$i$个元素所在位置的最长公共子序列。先找到字符串B的第一个字符在A中的位置，从此位置开始，之后的dp[i]都置为1；然后找B中第二个字符，找到之后，dp[i]=dp[i-1]+1（dp[i-1]在递推过程中会被覆盖，需要单独用变量保存）；找到之前，将沿途的dp[i]都设置为dp[i-1]和dp[i]二者中的最大值。
#include <algorithm>
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int dp[1001] = {0};
for(int i=0; i<=text1.length(); i++){
int m, n=0;
for(int j=0; j<=text2.length(); j++){
m = dp[j+1];
if(text2[j]==text1[i]){
dp[j+1]=n+1;
}else{
dp[j+1]=max(dp[j], m);
}
n = m;
}
}
return dp[text2.length()];
}
};- 使用滚动数组时，要注意上一位的数据会在递推时被覆盖，因此需要先保存一下，否则会出现错误的结果。
- 最长子序列的增长，是基于上一行上一列的值，也就是上一条说到的滚动数组中被保存的那个值，而不是基于该列上一行的值。否则最长子序列的数值会在同一个位置递增。
原谅我的没见识，这在大佬眼里肯定不算什么但是我现在真的好开心哈哈哈哈哈哈哈哈
最长递增子序列
我真是猪脑子，居然没想到办法……思路是，创建一个新的数组，将输入的数组复制到这个数组中，然后对这个新数组进行排序。接下来寻找新数组与输入的数组的最长公共子序列即可。因为原数组与排好序的数组的公共子序列一定是递增的。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> sorted = nums;
nums.swap(sorted);
sort(sorted.begin(), sorted.end());
vector<int>::iterator end = unique(sorted.begin(), sorted.end());
sorted.erase(end, sorted.end());
int dp[2501] = {0};
for(int i=0; i<sorted.size(); i++){
int m, n=0;
for(int j=0; j<nums.size(); j++){
m = dp[j+1];
if(nums[j]==sorted[i]){
dp[j+1]=n+1;
}else{
dp[j+1]=max(dp[j], m);
}
n = m;
}
}
return dp[nums.size()];
}
};另外一种时间复杂度可以达到$n\log_2n$的算法，非常有趣。以4, 8, 9, 5, 6, 7为例，创建一个新数组a，扫描原数组的同时，不断处理数组a。若当前扫描到的数字大于a中最后一个数组，则将数字接到a上，否则将当前数字替换到a中第一个大于当前数的位置。顺序示意如下：
- 4 8 9
- 4 5 9
- 4 5 6
- 4 5 6 7
得到的数组a并非就是最长递增子序列，这一点很容易验证，如4, 8, 9, 5，按照上面的方法得到的a就是4 5 9，这并不是原数组的子序列。但有趣的是a的长度和$LIS（最长递增子序列）$的长度相等。这个算法的原理是，若遇到更小的数字，则将其替换到前面去，这个替换的操作并不会影响$LIS$的长度，但是能为后面可能在$LIS$中的数字进入a数组提供机会。
实际编程时，不需要单独再开一个a数组，直接用原数组的空间即可。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = 1;
for(int i=1; i<nums.size(); i++){
if(nums[i]>nums[len-1]){
nums[len]=nums[i];
len++;
}
else{
int* p = &nums[0];
int *t = lower_bound(p, p+len-1, nums[i]);
if(t == p){
*t = nums[i];
}
else if(t > p && *(t-1)!=nums[i]){
*t = nums[i];
}
}
}
return len;
}
};递归+记忆化搜索
递归的过程中可能会产生许多重复的计算，如果对已经计算过的元素进行标记，就能识别哪些元素是被计算过的，就能避免重复计算。在保留递归的直观性的同时，还能获得很好的效率。
区间DP
dp[i][j] = min/max(dp[i][k] + dp[k+1][j]) + sum[i][j-i-1];在一个区间内寻找最优分割点。
石子合并
https://leetcode-cn.com/problems/minimum-cost-to-merge-stones/
这道题真的巨难，最后看题解看懂了，但是也不想写了，之后回来填坑吧……同志仍需努力啊！
回文串
POJ 3280
我是真的被一个点卡懵了，我真的被难哭了。
思路：
- 增删等价，因此只选择代价最小的
- 一定要从后往前推！因为递推时，需要用到状态矩阵左侧和下方的数据，因此需要从后往前推，即先生成状态矩阵下面的行，而每一行又是从左往右推。
#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 2010
int dp[MAX][MAX] = { 0 };
int main() {
int n, len;
cin >> n >> len;
char a[MAX];
int v[26];
cin >> a;
for (int i = 0; i < n; i++) {
char letter;
int c1, c2;;
cin >> letter >> c1 >> c2;
v[letter - 'a'] = c1 > c2 ? c2 : c1;
}
//for (int i = 0; i < len; i++) {
for (int i = len - 1; i >= 0; i--) {
for (int j = i + 1; j < len; j++) {
if (a[i] == a[j]) {
dp[i][j] = dp[i + 1][j - 1];
}
else {
dp[i][j] = min(dp[i + 1][j] + v[a[i] - 'a'], dp[i][j - 1] + v[a[j] - 'a']);
}
}
}
cout << dp[0][len-1] << endl;
}状态压缩DP
状态压缩DP是将一些难以用其他方式表达的状态以二进制、三进制等形式来表达。非常经典的例子就是用状压DP解决TSP问题（刚好智能车也要用到这个）。
状态转移方程：
当前已经访问过的集合为$S$，当前所在顶点为$v$，用$dp[S][v]$表示从$v$出发访问剩余所有节点，最终回到顶点0的权重和的最小值。从上述描述可以看出，这是一个倒推的过程，从$dp[V][0]=0$（已经访问了所有节点，当前站在0点，要前往0点，代价为0）开始往前推。$dp[S][v]=min{dp[S]\cup{u}}[u]+d(v,u)|\notin S$}
// 状态压缩DP
memset(dp, 5, sizeof(dp)); // 初始化为一个较大值
dp[(1 << num) - 1][0] = 0; // 从后往前递推，给第一个元素赋值
// 递推计算
for (int S = (1 << num) - 2; S >= 0; S--) {
for (int v = 0; v < num; v++) {
for (int u = 0; u < num; u++) {
if (!(S >> u & 1)) {
dp[S][v] = dp[S][v] < dp[S | 1 << u][u] + dp[v][u] ? dp[S][v] : dp[S | 1 << u][u];
}
}
}
}若用递归，则代码更加清晰明了，递归从起点开始往终点深入，在访问完所有点且站在0号点时开始返回。