动态规划（Dynamic Programming）

什么是动态规划？

动态规划是一种通过把原问题分解为相对简单的子问题的方式，利用子问题的最优解来求解复杂问题最优化解的方法。

核心思想：
把大问题分解成小问题（分治思想）

保存子问题的解，避免重复计算（记忆化）

通过子问题的解推导出原问题的解

特征

  1. 最优子结构

一个问题的最优解包含其子问题的最优解，可以通过组合子问题的最优解得到原问题的最优解

例子：最短路径问题
从A到C的最短路径 = 从A到B的最短路径 + 从B到C的最短路径

  1. 重叠子问题

在求解过程中，相同的子问题会被多次计算，动态规划通过存储计算结果避免重复计算

  1. 无后效性

未来的决策只取决于当前状态，与如何到达当前状态无关，”过去不影响未来”

啥时候能用

  1. 计数问题：有多少种方式/方法…

  2. 最值问题：最大值/最小值/最长/最短…

  3. 存在性问题：是否可能/能否实现…

  4. 问题可以被分解，且子问题重叠

1.洛谷P1433吃奶酪

题目：房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。

第一行有一个整数，表示奶酪的数量 n。

第 2 到第 (n+1) 行，每行两个实数，第 (i+1) 行的实数分别表示第 i 块奶酪的横纵坐标 x

​输出一行一个实数，表示要跑的最少距离，保留 2 位小数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>

using namespace std;

const int MAXN=15;
const double INF=1e18;

double x[MAXN],y[MAXN];
double dist[MAXN][MAXN];  //任意两点间的距离 
double startDist[MAXN];    //任意点离起点的距离 
double dp[1<<MAXN][MAXN];
//状态压缩DP数组，第一维是状态掩码
//第二维是最后一个奶酪的编号

int main(){
	int n;
	cin>>n;
	
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	
	//预处理距离
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			double dx=x[i]-x[j];
			double dy=y[i]-y[j];
			dist[i][j]=sqrt(dx*dx+dy*dy); 
		}
		startDist[i]=sqrt(x[i]*x[i]+y[i]*y[i]);
	} 
	
	//初始化dp数组，将所有状态设为无穷大
	int total=1<<n;
	for(int mask=0;mask<total;mask++){
		for(int i=0;i<n;i++){
			dp[mask][i]=INF;
			//访问了mask表示的奶酪集合
			//最后一个访问的是奶酪i的最短距离
		}
	} 
	
	//初始化，从原点直接到点i
	// 掩码1<<i表示只访问了第i个奶酪的状态
	for(int i=0;i<n;i++){
		dp[1<<i][i]=startDist[i];
	} 
	
	//状态转移
	for(int mask=1;mask<total;mask++){
		for(int i=0;i<n;i++){
			if(!(mask&(1<<i))) continue;
			for(int j=0;j<n;j++){
				if(mask&(1<<j)) continue;
				
				int newMask=mask|(1<<j);
				
				dp[newMask][j]=min(dp[newMask][j],dp[mask][i]+dist[i][j]);
			}
		}
	} 
	
	double ans = INF;
    int fullMask = total - 1;
     // 遍历所有可能的最后一个奶酪
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[fullMask][i]);
    }

    cout << fixed << setprecision(2) << ans << endl;
    return 0;
	
}