动态规划算法

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

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

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

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

如果不记录每一步的结果,动态规划的时间复杂度与Brute Force无异。动态规划实质上是一种以空间换时间的方法,通过存储过程中每一步骤的状态来降低时间复杂度。

举个栗子

我们以Leetcode的Climbing Stairs题目为例:

当前位置为第i级台阶时,有两种途径到达当前的状态:

  • 从第i-1级台阶走一步而来
  • 从第i-2级台阶走两步而来

因此,到达第i级台阶的途径为到达第i-1级台阶和到达第i-2级台阶的途径数量之和。我们可以得出如下的状态转移方程:

Leetcode笔记

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

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

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