DP

动态规划 Dynamic Programming

什么是动态规划

动态规划并不是指某一种具体的算法,更多的时候它是指代一直算法的思想

动态规划的三个条件

1. 存在最优子结构
2. 存在重复子问题
3. 动态

动态规划

动态规划五部曲

来自代码随想录的动态规划标准解法

1. 确定DP数组的含义
2. 确定DP数组初始化
3. 确定状态转移方程
4. 确定状态转移的方式
5. 确定得到的结果

常见问题

• 记忆化搜索

• 背包问题

• 钢条切割问题

// 钢条切割问题
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

struct Price{
    int length;
    int value;
};


class tr{
    int MaxValue(vector<Price> PriceList, int n) {
        map<int,int> PriceLists;
        for (int i = 0; i < PriceList.size(); i++) {
            if (PriceList[i].length <= n) {
                PriceLists[PriceList[i].length] = PriceList[i].value;
            }
        }
        
        vector<int>SumValue;
    }
} S;