第14章动态规划

动态规划

• 确定递推状态： f(n)+解释
• 确定递推公式
• 程序实现

  优化：

  
  （图片来源网络，侵删）
  • 去除冗余状态
  • 状态重定义
  • 优化转移过程
  • 斜率优化

    优化-递归+记忆化

    if arr[n] return arr[n]
    

    递归+记忆化(正向求解-递归) 或 改变求解顺序（逆向递归求解-循环） ： 解决效率问题

    用long long ，或者更大的：解决数值溢出，不够大问题

    HZOJ 38 兔子繁殖问题

    1. 确定递推状态： f(n)为第n个月的时候兔子的数量
    2. 确定递推公式: f(1)=1 | f(2)=2 | f(n)=f(n-1)+f(n-2)
    3. 程序实现

    #include 
    using namespace std;
    #define MAX_N 100
    int digui_jiyihua_arr[MAX_N+5]={0};
    int f(int n){
        if(n>n;
        cout