动态规划
- 507
这道题是最基础的斐波拉契数列，已经给出了转换关系dp[n]=dp[n-1]+dp[n-2]，没有什么好说的。这里我使用的是一个int类型的数组来存储每一次计算的值
for (int i = 2; i <= n; i++) {
arr[i] = arr[i - 2] + arr[i - 1];
}
如果我们使用自底向上的方法也不需要存储每一次所得到的dp的值，官方题解使用了几个变量来存储每一次的变换，可以降低空间复杂度。(如1137中使用到的)
- 1137
这题也是有一个很明显的递归关系Tn+3 = Tn + Tn+1 + Tn+2，与507类似，这里使用自底向上的动态规划，使用几个变量来存储每一次变换后的值，如下，可以降低算法的空间复杂度
int a = 0, b = 1, c = 1, result = 0;
for (int i = 3; i < n; i++) {
result = a + b + c;
a = b;
b = c;
c = result;
}
- 2469(每日一题）
没啥写的。。 - 217
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
第一想法使用map，如果map里面包含某个key说明重复了，此时时间复杂度为O(n)，相当于把整数数组遍历一遍。
题解还说可以先排序，再比较相邻两个元素的大小。使用java中的api,Arrays.sort(),快速和合并一起用的，时间复杂度为NlogN。
这题考动态规划，属于是打脑壳。