动态规划总结

动态规划算法的设计主要有以下４个步骤
(1) 描述最优解的结构
(2) 递归定义最优解的值
(3) 按自底向上的方式计算最优解的值
(4) 由计算出的结果构造一个最优解

其实最核心的步骤是　定义一个描述最优解的递归公式 (状态转移方程)

git 安装

sudo apt-get install git 

github 配置

需要在github创建一个名称为username.github.io的项目
同时配置ssh，可以连接github，详情看　

https://help.github.com/articles/connecting-to-github-with-ssh/

question：

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

question

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

     _______6______
    /              \
 ___2__           ___8__
/      \         /      \
0      _4        7       9
      /  \
     3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

question

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.