DP

一.什么是动态规划？

---

“递推”：   

Example 1: 斐波那契数列

1 1 2 3 5 8 13 21 ……

Example 2: 求最短路径

“本质”：——状态，状态转移方程，无后效性 - 局部最优全局最优

Example3: f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j]

无后效性：局部最优    不会导致     全局不是最优

---

二.常见题型

---

LEET CODE 300. 

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,

Given [10, 9, 2, 5, 3, 7, 101, 18],

The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

LEET CODE 265.

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:

All costs are positive integers.

Follow up:

Could you solve it in O(nk) runtime?

01背包问题：

你有一个容量为M的背包。现在有N个物品摆在你的面前，每个物品有Ai的价值，占Bi的空间。如何用M的空间装走尽量多价值的物品。

FOLLOW UP:并且输出你选择了哪几个物品

LEET CODE 486

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

---

300.f[i]=f[j]+1  (a[j]<=a[i]  && j<i)

265.f[i][j]=min(f[i-1][k]  ( k != j)  )+a[i][j]

486. f[i][j] = max (g[i][j]-f[i+1][j],g[i][j]-f[i][j-1])