dp动态规划分享

dp动态规划分享

什么是动态规划 ？

动态规划（Dynamic Programming，简称DP）是一种算法设计技巧，用于解决具有重叠子问题和最优子结构特性的问题。它是一种将复杂问题分解成更简单的子问题，并通过存储这些子问题的解来避免重复计算的方法。动态规划通常用于优化问题，特别是在计算数学、管理科学、经济学、计算机科学等领域。

动态规划的核心概念

1. 重叠子问题（Overlapping Subproblems）： 在递归算法中，相同的子问题被多次解决。例如，在斐波那契数列的递归实现中，Fib(n) 会多次计算 Fib(n-1) 和 Fib(n-2)。动态规划通过存储这些子问题的解来避免重复计算。

2. 最优子结构（Optimal Substructure）： 一个问题的最优解包含其子问题的最优解。例如，在背包问题中，整个背包的最优装载方式可以由各个子背包的最优装载方式组合而成。

3. 无后效性（Non-Overlapping Property）： 一旦某个状态的最优解被确定，它不会受到之后决策的影响。这意味着，对于每个状态，我们只需要考虑如何从之前的状态到达当前状态，而不需要考虑未来的状态。

动态规划的使用

1. 什么时候用DP?
   当满足最优子结构和无后效性这两个性质。
   a. 大问题的最优解可以由小问题的最优解推出，这个性质就叫做“最优子结构”。
   b. 无后效性指的是在动态规划问题中，一旦某个状态的最优解被确定，它不会受到之后决策的影响。换句话说，对于动态规划中的每个状态，其最优解只依赖于之前的状态，而不依赖于之后的状态。

2. 怎么用DP ？
   a.状态设计:
   将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）
   b.状态转移:
   寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
   c.编码实现
   自顶向下：用带记忆化的递归编码（Top-Down ，先大问题再小问题）

   自下而上：用递推编码（Bottom-Up，先小问题再大问题）

3. 斐波那契数列实现

   #include<bits/stdc++.h>
   using namespace std;
   const int N = 42;            //因为斐波那契数增长太快，这里只算41个数
   int dp[N];                  //记忆结果
   int fib (int n){
       if (n == 1 || n == 2)  return 1;
       if(dp[n] != 0) return dp[n];  //已经计算过，直接返回结果，不再递归
       dp[n]= fib (n - 1) + fib (n - 2);    //递归计算，并记忆
       return dp[n];
   }
   int main(){
       cout << fib(41);       //计算第41个斐波那契数: 165580141
   }