动态规划笔记

这里主要介绍两种情形：

1. 小偷偷一排店铺，被偷的店铺不能连着，否则报警。

   6,3,1,5,2,7

偷到的最大价值是 6+5+7=18

定义问题： dp[i] 表示前i个店铺偷到的最大值，

               dp[i] = max(dp[i-2]+a[i],dp[i-1]);

另外，本体也可以用记忆化搜索：

       mem[i] 表示以第i个店铺结尾的店铺的最大值，

       mem[i] = max(mem[i-2],mem[i-3]) + a[i];

  res= max(mem);

2. 最大上升子序列（不考虑辅助数组）

1,5,2,3,1,9

结果：1,2,3,9

定义问题：

     dp[i] 表示以a[i]结尾的当前最长上升子序列。

注意：这里不能把dp[i] 定义成前i个序列中最长上升子序列。

   int tem =0;

    for k= 1 to i

         if(a[k]<a[i])  

            tem = tem > dp[k]+1?tem:dp[k]+1;

由于每次需要向前遍历，故时间复杂度O(n^2)。

 

比较两者的区别：

Q1研究的序列，前后总的结果有关系，但是前后具体元素之间大小没有比较约束

Q2研究的序列，前后总的结果也有关系，但前后具体元素之间有大小约束关系！

小结：

凡是前后元素大小或者先后次序有约束的，定义问题时：

均不能使用前i个。。。，

而是用：以第i个结尾的情况下，。。。。（此种方法是通用的，无前后元素大小或者先后次序有约束的也可用）