以前有个孩子，他分分钟都在碎碎念。不过，他的念头之间是有因果关系的。他会在本子里记录每一个念头，并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子，你一定会被互相穿梭的箭头给搅晕，现在他希望你用程序计算出这些念头中最长的一条因果链。
将念头从1到n编号，念头i来源于念头from[i]，保证from[i]<i，from[i]=0表示该念头没有来源念头，只是脑袋一抽，灵光一现。

第一行一个正整数n表示念头的数量
接下来n行依次给出from[1]，from[2]，…，from[n]

共一行，一个正整数L表示最长的念头因果链中的念头数量

8
0
1
0
3
2
4
2
4

3

最长的因果链有：
1->2->5 (from[5]=2,from[2]=1,from[1]=0)
1->2->7 (from[7]=2,from[2]=1,from[1]=0)
3->4->6 (from[6]=4,from[4]=3,from[3]=0)
3->4->8 (from[8]=4,from[4]=3,from[3]=0)

1<=n<=1000

## 蓝桥杯 ALGO-11 算法训练 瓷砖铺放（递归/动态规划）

有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？
例如，长度为4的地面一共有如下5种铺法：
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
编程用递归的方法求解上述问题。

只有一个数N，代表地板的长度

输出一个数，代表所有不同的瓷砖铺放方法的总数

4

5

## LeetCode上Tag为动态规划(Dynamic Programming)的题目整理

120. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[[2],
[3,4],
[6,5,7],
[4,1,8,3]]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

1.当 n == 0 时，return 0
2.当 n == 1 时，return nums[0]
3.当 n >= 2 时，创建数组 dp[n]表示从0~n-1家能够抢到的最大值
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
dp[i] = max(dp[i – 2] + nums[i], dp[i – 1]);

213. House Robber II
Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

0.不包括最后一个屋子~就抢劫0~n-2号屋子~
1.不包括第一个屋子~就抢劫1~n-1号屋子~

121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

minvalue 中保存从0到当前所有股价中最低的价格
ans 中保存minvalue到当前所有股价中能卖掉的最高的价格

303. Range Sum Query – Immutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.

70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
update: v2.0：  //可以把递归改成更简单易懂的递推：

338. Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

1.v[0] = 0
2.v[i] = v[i << 1] + i % 2

62. Unique Paths
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?//这题目还有个萌萌的小插图，如下~：

63. Unique Paths II
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.

0.a[0][0] = 1;
1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以a[i][j] = a[i][j-1];
2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以a[i][j] = a[i-1][j];
3.其余情况，当前方格能由左边和上边两个方向过来，所以a[i][j] = a[i-1][j] + a[i][j-1];

64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

0.当i == 0 && j == 0的时候，dp[i][j] = grid[i][j];
1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以dp[i][j] = dp[i][j-1] + grid[i][j];
2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以dp[i][j] = dp[i-1][j] + grid[i][j];
3.其他情况下，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

0.ans始终为temp和ans值中较大的那一个。
1.当当前temp的值为正数的时候，来者nums[i]加temp。//此时如果nums[i]为负数对临时总和temp无贡献，则不会更新ans的值，我们临时把它收入temp的总和当中以备后用。如果nums[i]是正数，对临时总和temp有贡献，那就会更新ans的最大值。
2.当当前temp的值为负数的时候，temp的值直接+nums[i]。//之前的临时总和temp是个负数，对于来者nums[i]来说不管怎样nums[i]如果+temp都是在减少nums[i]，还不如直接将temp=0舍弃前面的负数和，取nums[i]当作当前的临时总和的值。
3.temp如果为0不用考虑怎样都行~

96. Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

v[i-j]等于root结点右边i-j个结点能构成的BST个数~//j+1~i的种数和0~i-j的种数一样。。所以就是v[i-j]~

j可以取1~i中的任意一个值，把这些所有计算出来的总数相加就是v[i]的值~~~~

v[i] += v[j-1] * v[i-j];
}

300. Longest Increasing Subsequence
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?
update v2.0: //更高效的O(nlogn)方法~

v 1.0：

dp数组dp[i]的值表示nums[i]处可以构成的最长字串的长度~~

304. Range Sum Query 2D – Immutable
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).
The number of ways decoding “12” is 2.

0.如果说当前s[i]不等于0,那先令dp[i] = dp[i-1]
1.如果s[i-1]与s[i]能够构成1~26里面的数字，那就把s[i-1]与s[i]构成一个整体，dp[i] += dp[i-2];

279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.