网站导航
> 技术文档 > 动态规划技术总结

动态规划技术总结

网友: 技术文档 2025-08-08 08:46:31

动态规划

什么是动态规划？ 动态规划（Dynamic Programming，简称 DP）是一种解决最优化问题的算法思想，特别适用于具有 重叠子问题 和 最优子结构 的问题。它的核心思想是将问题分解成子问题，通过保存子问题的结果（通常使用数组或表格）避免重复计算，从而提高效率。

1. 线性动态规划

线性动态规划是指问题的状态可以用一个线性结构（如数组的一维索引）来表示和转移的动态规划。

核心结构：

  • 状态：通常是一个数组，例如 dp[i]dp[i]dp[i]

  • 状态转移：从前一个状态推导出当前状态，例如 dp[i]=dp[i−1]+...dp[i] = dp[i-1] + ...dp[i]=dp[i−1]+...

  • 初始化与边界处理是关键

1.1 线性动态规划的几种类型

类型 典型问题 状态示例 基本递推型 斐波那契数列、爬楼梯问题 dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]dp[i]=dp[i−1]+dp[i−2] 最大子序列型 最大连续子数组、打家劫舍 dp[i]=max(dp[i−1],nums[i]+...)dp[i] = max(dp[i-1], nums[i] + ...)dp[i]=max(dp[i−1],nums[i]+...) 背包型 01 背包、完全背包 dp[i]=max(dp[i],dp[i−w]+v)dp[i] = max(dp[i], dp[i-w] + v)dp[i]=max(dp[i],dp[i−w]+v) 最长序列型 最长递增子序列、LIS、LCS dp[i]=max(dp[j]+1)dp[i] = max(dp[j] + 1)dp[i]=max(dp[j]+1)

1.2 线性动态规划代码实现(爬楼梯问题)

import java.util.*;public class Main {  public static void main(String[] args) {  Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 总阶数 if (n <= 2) {  System.out.println(n); return; } int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++</
网络标签：

相关问题