hello算法之动态规划

创建时间: 2026-07-13 18:24:18

动态规划

动态规划(dynamic programming)是一个重要的算术范式,它将一个问题分解为一系列更小的子问题,并通过存储子问题的解来避免重复计算,从而大幅提升时间效率。

现在有一个题目如下:

给定一个共有n阶的楼梯,你每步可以上1阶或者2阶,请问有多少种方案可以爬到楼顶?

这个题目的目标是求解方案数量,我们可以考虑通过回溯来穷举所有可能性。具体来说,将爬楼梯想象为一个多轮选择的过程:从地面出发,每轮选择上1阶或者2阶,每当到达楼梯顶部时就将方案数量加1,当越过楼梯顶部时就将其剪枝。代码如下:

void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {
	if(state == n)
		res[0]++;
	for(auto &choice : choices) {
		if (state + choice > n)
			continue;
		backtrack(choices, state + choice, n, res)
	}
}

int climbStairsBacktrack(int n) {
	vector<int> choices = {1, 2};
	int state = 0;
	vector<int> res = {0};
	backtrack(choices, state, n, res);
	return res[0];
}

方法一:暴力搜索

int dfs(int i) {
	if(i == 1 || i == 2)
		return i;
	int count = dfs(i-1) + dfs(i - 2);
	return count;
}

int climbingStairsDFS(int n) {
	return dfs(n);
}

方法二:记忆搜索

为了提升算法效率,我们希望所有的重叠子问题都只被计算一次。为此,我们声明一个数组mem来记录每个子问题的解,并在搜索过程中将重叠子问题剪枝。

  1. 当首次计算dp[i]时,我们将其记录至mem[i],以便之后使用。
  2. 当再次需要计算dp[i]时,我们便可直接从mem[i]中获取结果,从而避免重复计算该子问题。
int dfs(int i, vector<int> &mem) {
	if(i == 1 || i == 2)
		return i;
	if(mem[i] != -1)
		return mem[i];
	int count = dfs(i-1, mem) + dfs(i - 2, mem);
	mem[i] = count;
	return count;
}

int climbingStairsDFS(int n) {
	vector<int> mem(n+1, -1);
	return dfs(n, mem);
}

方法三:动态规划

记忆优化搜索是一种“从顶至底”的方法:我们从原问题(根节点)开始,递归地将较大子问题分解为较小子问题,直至解已知的最小子问题(叶节点)。之后,通过回溯层收集子问题的解,构建出原问题的解。

与之相反,动态规划是一种“从底至顶”的方法:从最小子问题的解开始,迭代地构建更大问题的解,直至得到原问题的解。

由于动态规划不包含回溯过程,因此只需要使用循环迭代实现,无须使用递归。在以下代码中,我们初始化一个数组dp来储存子问题的解,它起到了与记忆优化搜索中数组mem相同的记录作用:

int climbingStairsDP(int n) {
	if(n == 1 || n == 2)
		return n;
	vector<int> dp(n+1);
	dp[1]=1;
	dp[2]=2;
	for(int i = 3; i <= n; i++) {
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[n];
}

空间优化

int climbingStairsDP(int n) {
	if(n == 1 || n == 2)
		return n;
	int a = 1, b = 2;
	for(int i = 3; i <= n; i++) {
		int tmp = b;
		b = a + b;
		a = tmp;
	}
	return b;
}

动态规划问题特性

前面学习了动态规划如何通过子问题来解决求解原问题的。实际上,子问题分解是一种通用的算法思路,在分治、动态规划、回溯中的侧重点不同。

  • 分治算法递归地将原问题划分为多个互相独立的子问题,直至最小子问题,并在回溯中合并子问题的解,最终得到原问题的解。
  • 动态规划也对问题进行递归分解,但与分治算法的主要区别是,动态规划中的子问题是互相依赖的,在分解过程中会出现许多重叠子问题。
  • 回溯算法在尝试和回退中穷举所有可能的解,并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成,我们可以将每个决策步骤之前的子序列看作一个子问题。

实际上,动态规划常用来求解最优化问题,它们不仅包含重叠子问题,还具有另外两大特性:最优子结构、无后效性。

最优子结构

我们对爬楼梯问题稍做改动,使之更加合适展示最优子结构概念。

int minCostClimbingStairs(vector<int> &cost) {
    int n = cost.size() - 1;
	if(n == 1 || n == 2)
		return cost[n];
	vector<int> dp(n+1);
	dp[1] = cost[1];
	dp[2] = cost[2]
	for(int i = 3; i <= n; i++) {
		dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
	}
}

可以对上述代码进行空间优化

int minCostClimbingStairsDPComp(vector<int> &cost) {
	int n = cost.size() - 1;
	if(n == 1 || n == 2)
		return cost[n];
	int a = cost[1], b = cost[2];
	for(int i = 3; i <= n; i++) {
		int tmp = b;
		b = min(a, b) + cost[i];
		a = tmp;
	}
	return b;
}

动态规划解题思路

上面介绍了动态规划问题的主要特征,下面来研究两个更加实用的问题。

  1. 如何判断一个问题是不是动态规划问题?
  2. 求解动态规划问题该从何入手,完整步骤是什么?

问题判断

总的来说,如果一个问题包含重叠子问题、最优子结构,并满足无后效性,那么它通常适合用动态规划求解。然而,我们很难从问题描述中直接提取出这些特性。因此我们通常会放宽条件,先观察问题是否使用回溯(穷举)解决。

适合用回溯解决的问题通常满足“决策树模型”,这种问题可以使用树形结构来描述,其中每一个节点代表一个决策,每一条路代表一个决策序列。

换句话说,如果问题包含明确的决策概念,并且解是通过一系列决策产生的,那么它就满足决策树模型,通常可以使用回溯来解决。

在此基础上,动态规划问题还有一些判断的“加分项”。

  • 问题包含最大(小)或最多(少)等优化描述。
  • 问题的状态能够使用一个列表、多维矩阵或树来表示,并且一个状态与其周围的状态存在递推关系。

相应地,也存在一些“减分项”。

  • 问题的目标是找出所有可能的解决方案,而不是找出最优解。
  • 问题描述中有明显的排列组合的特征,需要返回具体的多个方案。

如果一个问题满足决策树模型,并具有较为明显的“加分项”,我们就可以假设它是一个动态规划问题并在求解中验证它。

问题求解步骤

动态规划的解题流程会因问题的性质和难度而有所不同,但通常遵循以下步骤:描述决策,定义状态,建立dp表,推导状态转移方程,确定边界条件等。

为了更形象地展示解题步骤,我们使用一个经典问题“最小路径和”来举例。

给定一个n*m的二维网格grid,网格中的每个单元格包含一个非负整数,表示该单元格的代价。机器人以左上角单元格为起始点,每次只能向下或者向右移动一步,直至到达右下角单元格。请返回从左上角到右下角的最小路径和

方法一:暴力搜索

int minPathSumDFS(vector<vector<int>> &grid, int i, int j) {
	if(i == 0 && j == 0) {
		return grid[0][0];
	}
	if(i < 0 || j < 0) {
		return INT_MAX;
	}
	int up = minPathSumDFS(grid, i-1, j);
	int left = minPathSumDFS(grid, i, j-1);
	return min(up, left) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
}

方法二:记忆搜索

int minPathSumDFS(vector<vector<int>> &grid, int i, int j, vector<vector<int>> &mem) {
	if(i == 0 && j == 0) {
		return grid[0][0];
	}
	if(i < 0 || j < 0) {
		return INT_MAX;
	}
	if(mem[i][j] != -1) {
		return mem[i][j];
	}
	int up = minPathSumDFS(grid, i-1, j, mem);
	int left = minPathSumDFS(grid, i, j-1, mem);
	mem[i][j] = min(up, left) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
	return mem[i][j];
}

方法三:动态规划

int minPathSumDP(vector<vector<int>> &grid) {
	int m = grid.size(), n = grid[0].size();
	vector<vector<int>> dp(m, vector<int>(n));
	dp[0][0] = grid[0][0];
	for(int i = 1; i < m; i++) {
	    dp[0][j] = dp[0][j-1]+grid[0][j];
	}
	for(int i = 1; i < n; i++) {
	    dp[i][0] = dp[i-1][0]+grid[i][0];
	}
	for(int i = 1; i < m; i++) {
		for(int j = 1; j < n; j++) {

			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
		}
	}
	return dp[m-1][n-1];
}

0-1 背包问题

背包问题是一个非常好的动态规划入门题目,是动态规划中最常见的问题形式。其具有很多变种,例如0-1背包问题、完全背包问题、多重背包问题等。

给定n个物品,第i个物品的重量为wgt[i-1]、价值为val[i-1],和一个容量为cap的背包。每个物品只能选择一次,问在限定背包容量下能放入物品的最大价值。

方法一:暴力搜索

int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) {
	if(i == 0) {
		return 0;
	}
	if(wgt[i-1] > c) {
		return knapsackDFS(wgt, val, i-1, c);
	}
	int no = knapsackDFS(wgt, val, i-1, c);
	int yes = knapsackDFS(wgt, val, i-1, c-wgt[i-1]) + val[i-1];
	return max(no, yes);
}

方法二:记忆搜索

int knapsackDFSMem(vector<int> &wgt, vector<int> &val, vector<vector<int>> &mem, int i, int c) {
	if(i == 0 || c == 0) {
		return 0;
	}
	if(mem[i][c] != -1) {
		return mem[i][c];
	}
	if(wgt[i-1] > c) {
	    return knapsackDFSMem(wgt, val, mem, i - 1, c);
	}
	int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
	int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
	mem[i][c] = max(no, yes);
	return mem[i][c];
}

方法三:动态规划

int knapsackDP(vector<int> &wgt, vector<int> &val, int c) {
	int n = wgt.size();
	vector<vector<int>> dp(n + 1, vector<int>(c + 1));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= c; j++) {
			if(wgt[i-1] > j) {
				dp[i][j] = dp[i-1][j];
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-wgt[i-1]] + val[i-1]);
			}
		}
	}
	return dp[n][c];
}