2017年11月26日00:08:06

时间总是容自己控制，本来很早就能把报告总结完，案例分析完，就是期间有重要的聊天，最后匆匆的写完报告去睡觉了。

以下是word内容：

我理解中的动态规划：

把一个问题分解成多个问题，按顺序求解子问题，前一子问题的解，为后一子问题提供有用的信息。求每个子问题是，解出各个局部的解，通过决策达到那些最优的局部解，其他的解丢弃。依次解决各个子问题，解到最后一个就是厨师问题的解。

动态规划使用的情况：

采用动态规划求解的问题一般需要3个性质：

1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，既满足最优化原理。
2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

动态规划算法题：

首先，我们看一下这道题（此题目来源于北大POJ）：

 数字三角形(POJ1163)

    在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100，数字为 0 - 99

样式输入：

5      //表示三角形的行数    接下来输入三角形

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5

样式输出

30

   解题思路：

要求输出最大和

首先，肯定得用二维数组来存放数字三角形

然后建一个数组来存放子问题的解。

利用max（a，b）+arr[i][j]，解除算一个子问题，max（a,b）是去出重复的计算。

实现代码：

下午的模拟考试8道题做出三道，做出了三道题中有一道题有那么点难，其他题用代码不知道怎么实现，但是想法却有的。

描述

传说某凡学长在给学弟出题的时候，总是会自认为题的数据量很大，然而每次都会让学弟轻松的拿暴力跑过去，因此每次凡学长的心态都十分崩溃。而这次，学弟本是想回敬一道数据量灰常大的主席树,套水仙花数,套最小生成树,套伸展树，但是出于照顾凡学长心态的考虑， 就换成了这道防AK题。^_^

正如一般的算法题一样，我这里也在前面说了一堆废话。

在一天凡学长给”炸酱面”同学为了这次编程大赛做算法训练时，突然向这位同学提出了q个问题！假如有n道题，每道题做对会拿到Ai块钱，

（1<=i<=n）， (-10^9 <= A[i] <= 10^9),凡学长每次问这位学弟假如他会做从第i道题开始（包括i在内），在这之后(包括第i道题)总共连续的k道题，他想知道他会收到多少钱。

输入

Input
第1行：一个数N，N为数组的长度(2 <= N <= 50000)。
第2 至 N + 1行：数组的N个元素。(-10^9 <= A[i] <= 10^9)
第N + 2行：1个数Q，Q为查询的数量。Q<=1000000
第N + 3 至 N + Q + 2行：每行2个数，i，K（1 <= i <= N，0<=K+ i -1 <= N)

输出

对于每个询问。输出可以拿到的钱数。

样例输入1

5

1

3

7

9

-1

4

1 2

2 2

3 2

1 5

样例输出1

4

10

16

19

解题思路：

用一维数组去装Ai，用二维数组去装i和k。

解题的时候就用i和k的二维数组去一维数组中遍历，从i开始遍历K次。

解题代码：

Array和arrayList

新学的数组方法

1）Java中Array与ArrayList的主要区别：
可以将 ArrayList想象成一种“会自动扩增容量的Array”。

2）Array（[]）：最高效；但是其容量固定且无法动态改变；
ArrayList：  容量可动态增长；但牺牲效率；

3）基于效率和类型检验，应尽可能使用Array，无法确定数组大小时才使用ArrayList！
不过当试着解决更一般化的问题时，Array的功能就可能过于受限。

4）Java中一切皆对象，Array也是对象。不论所使用得Array型别为何，

Array名称本身实际上是个reference，指向heap之内得某个实际对象。

这个对象可经由“Array初始化语法”被自动产生，也可以以new表达式手动产生。

5）Array可做为函数返回值，因为它本身是对象的reference；

6)对象数组与基本类型数组在运用上几乎一模一样，唯一差别在于，前者持有得是reference，后者直接持有基本型别之值；
例如：
string [] staff=new string[100];
int [] num=new int[10];

7）对数组的一些基本操作，像排序、搜索与比较等是很常见的。因此在Java中提供了Arrays类协助这几个操作：sort(),binarySearch(),equals(),fill(),asList().

不过Arrays类没有提供删除方法，而ArrayList中有remove()方法，不知道是否是不需要在Array中做删除等操作的原因（因为此时应该使用链表）。

8）ArrayList的使用也很简单：产生ArrayList，利用add()将对象置入，利用get(i）配合索引值将它们取出。这一切就和Array的使用方式完全相同，只不过少了[]而已。

2.参考资料：
1）效率：
数组扩容是对ArrayList效率影响比较大的一个因素。
每当执行Add、AddRange、Insert、InsertRange等添加元素的方法，都会检查内部数组的容量是否不够了，如果是，它就会以当前容量的两倍来重新构建一个数组，将旧元素Copy到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。

ArrayList是Array的复杂版本
ArrayList内部封装了一个Object类型的数组，从一般的意义来说，它和数组没有本质的差别，甚至于ArrayList的许多方法，如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法。

2）类型识别：
ArrayList存入对象时，抛弃类型信息，所有对象屏蔽为Object，编译时不检查类型，但是运行时会报错。
ArrayList与数组的区别主要就是由于动态增容的效率问题了

3）ArrayList可以存任何Object，如String等。