动态规划算法

动态规划是一种分治(Divide&Conquer)的思想。在将大问题化解为小问题的分治过程中,保存对这些小问题已经处理好的结果,并供后面处理更大规模的问题时直接使用这些结果。

适用于动态规划的问题,需要满足最优子结构和无后效性两种情况。

  • 最优子结构性即如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。
  • 无后效性即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。

动态规划最重要的两个要点在于找到状态和状态转移方程,也就是递推关系。

Leetcode笔记

最近开始刷leetcode,在这里记录一下做题的过程,不定期更新。

GitHub:https://github.com/nyanim/leetcode

Algorithm

Two Sum(Easy)

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

解法1:暴力搜索

题目本身很简单,使用两个for循环遍历即可。需要注意的是同一元素不能使用两次,因此在遍历时,内层循环需要直接从外层循环+1处开始,而不是从头开始。

Solution:https://github.com/nyanim/leetcode/blob/master/TwoSum.py

解法2:哈希表

新建一个哈希表(Python中使用字典即可),遍历数组,以数组中的值为哈希表的键,以数组中的键为哈希表的值,将数组中的内容存入哈希表。

在遍历的同时检查(target-当前遍历到的值)是否存在哈希表的键中,如果存在则返回哈希表中的值和当前遍历到的键。这样复杂度由O(n^2)降低至O(n)。

Solution:https://github.com/nyanim/leetcode/blob/master/TwoSum(Hashmap).py