求助，关于动态规划如何学习

插个眼

cy

戒骄戒躁，学就完了

见一个记一个就完了，都是套路题

背

学动态规划之前，要先学会打暴力。
比如说IOI串，今年的山东CSP小学组第二题，这类题目如果打暴力，要怎么做？
最暴力的解法是枚举所有长度是n的IO串，然后判断题目给的串改成这个串代价是多少，复杂度n*2^n；
稍微一想就会发现，题目要求里满足条件的串其实没那么多，那就想想满足IOI这样形式的串一共有多少种，I和O的分界点是区分不同IOI串的关键，它有n^2个，加上和输入串的对比，复杂度从上一个方法降到了n^3
再进一步，并不是非得把结果的IOI串构造出来，才能知道输入串改过去的代价是多少，结果IOI串的形式就是下标i之前和j之后是I，中间是O，只需要统计输入串这三个区间里I和O各自的数量，用前缀和的方法可以把这个解法优化到n^2
此时才到了考虑动态规划的时候，上一个解法说到的3个区间，就是解决这个问题的阶段划分：先把第一个区间的I改好，再把第二个区间的O改好，最后改第三个区间的I。字符是从左到右一个一个改过去的，后面改的字符不影响之前的决策，所以动态规划的两个维度就出来了，这样复杂度降到n
楼主可以看看自己的思路卡在哪一个解法上，连暴力拿部分分数都做不到的话，就先不要什么题都试图用dp做

如果i+1的状态需要i和i-1的状态作为条件，这样如果计算n+1的状态就需要计算n和n-1的状态，计算n的状态就需要计算n-1和n-2的状态，这样n-1的状态就重复计算了
动态规划的原理是：
如果已经计算出了k的状态，就直接把这个状态缓存下来，下次需要计算这个状态时直接从缓存里取这个值，就省去了重新计算k的状态的操作
需要重复计算的项越多，动态规划的效果就越好，如果i+1状态只和i状态有关，那么动态规划基本就没有性能提升
拿最简单的动态规划的斐波拉契数列举例子：
暴力解是：
int fib(int n){
if (n == 1 || n == 2){
return 1;
}
return fib(n-1) + fib(n-2);
}
这样
1. 计算fib(5)，就需要计算fib(3)和fib(4)；
2. 计算fib(3)需要计算fib(1)和fib(2)，计算fib(4)需要计算fib(3)和fib(2)
3. 计算fib(3)需要计算fib(1)和fib(2)
这样fib(3)就重复计算了1次
n越大，重复计算的次数就越多
如果使用一个缓存来保存中间的计算步骤，就可以省去很多重复的计算：
int fib(int n){
static int arr[100] = {0,1,1};
if(arr[n] == 0){//如果已经计算过n
arr[n] = fib(n-1) + fib(n-2);
}
return arr[n];
}
把尾递归改成循环：
int fib(int n){
static int arr[100] = {0,1,1};
static int index = 2;
while(index < n){
arr[index+1] = arr[index] + arr[index-1];
}
return arr[n];
}
这就是一个常规意义上的动态规划的版本了。

IOI 串的问题：很容易看出来题目是要求把一个数组变成I..IO..OI..I的状态
假设第i个位置是O的起点，第J个位置是第二个I的起点
暴力解就是：
for(int i = 1; i < size-1; i++) {
for(int j = i+1; j < size; j++) {
统计:
a = [0,i)中O的数量
b = [i,j)中I的数量
c = [j,size)中O的数量
}
}
结果就是a+b+c
显然IO的数量可以用前缀和优化重复计算的问题

动态规划顾名思义就是动态做规划，从一个分支回溯上来的过程中，重新做下规划，好让下次搜索少走点弯路，要从头想明白这些本来就不简单，见的多了思路才多