递归思想

拿到一个问题，如何分析问题的递归性质

递归与非递归

递归与动态规划

分析

1.递归问题是否都可以使用动态规划来解决？
满足条件f(n1,n2,n3)=f(n1-k1,n2-k2,n3-k3)
0<=k1,k2,k3 是否就可以通过动态规划来解决递归问题

2.可以使用动态规划解决的问题是否都是递归类型的问题

特征

Meet In The Middle

描述

Meet in the Middle is an algorithmic technique that allows you combine results from two recursive calls efficiently.

Examples where it works:

Find 2 numbers from an array such that their sum is S. Complexity from O(N2) -> O(N)
Knapsack Problem
It works by in the following manner:

Break the given problem into two parts of equal length.
Find solutions to the two parts using brute force.
Now combine the results by picking an element in the first solution set, and searching for a corresponding element in the second solution set.
Notice that the above operation can only be done when merging the two solutions is an aggregate function. (Sum, Count, Max, Min…)
Return the result.
The time complexity of a problem goes from O(Nb) to O(N(b/2)). We see that the time complexity is still exponential, but the exponent is halved.

So, if we have N = 2 and b = 50,
Standard algorithm time: 250 = 12 days!
Meet in the Middle : 225 = 1 Second!

2.
Meet in the middle is a search technique which is used when the input is small but not as small that brute force can be used. Like divide and conquer it splits the problem into two, solves them individually and then merge them. But we can’t apply meet in the middle like divide and conquer because we don’t have the same structure as the original problem.

空间压缩

思想描述

离散化让空间压缩。
有一组数 x1，x2,x3,x4,x5…x(n-1),xn;
最大数为max(xi) 空间大小为max(xi)

对数组进行排序：
xs1,xs2,xs3.. xs(n-1),xs(n);

这n个数去掉重复的数后的数量为nc;
xs1,xs2,xs3.. xs(nc-1),xs(nc);
空间大小为nc

将空间从max(xi) 压缩到了nc

线段树

矩阵连乘

问题描述

给定n个矩阵｛A1,A2,…,An｝，其中，Ai与Ai+1是可乘的，(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的次数最小。

例如：

 A1是A（5*10）的方阵；

 A2是A（10*100）的方阵；

 A3是A（100*2）的方阵；

那么有两种加括号的方法：

  1. （A1A2）A3；
  2.   A1（A2A3）；

  第一种方法的计算量：5*10*100+5*100*2=6000；

  第二种方法的计算量：10*100*2+5*10*2=2100；  

问题分析

整数拆分

问题描述

一个正整数N,将其拆分成任意个正整数，使得所有的正整数乘机最大化
N=n1+n2+n3+…+n(i-1) + ni; (0<i<=N)
n1n2n3…n(i-1) ni 乘积最大

问题分析

递归性质
f代表数字n分成i个正整数可以获得的最大乘积
f(n,i) = f(n-j,i-1) * j (0<j<n-i)
f(n) = max(f(n,1),f(n,2),… f(n,i-1),f(n,(i)))

f代表数字n可以获得的最大乘积
fi代表数字n获得最大乘积时要拆分的个数
f(n)=max(f(n-j) * j) (0<j<n-j)
fi(n)=fi(n-j) + 1

代理模式

作图工具

UML

StarUML

axure

xmind

visio

PS

Shaping Regions