线性动态规划（一）

Posted on |

动态规划


斐波那契数列

递归版本:

求F(n)

if (n==0 || n==1) return 1；

else return F(n-1) + F(n-2);

重复子问题
导致算法效率低下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package Solution;

public class solution {
	public static void main(String[] args){
		 int[] a=new int[10];
		  a[0]=1;
		  a[1]=1;
int sum=cal(3,a);
System.out.println(sum);
  }
 static int cal(int n,int[] a){
	 
	  if(a[n]!=0)return a[n];
	  else return (a[n]=cal(n-1,a)+cal(n-2,a));
	  
	  
  }
}

相当于递推

1
2
3
4
A[0] = A[1] = 1;
for (i =2; i <= n ; i++)
	A[i]=A[i-1] + A[i-2];
return A[n];

算法复杂度是 O(n) 记忆化搜索

数组等将已经算过的东西记录下来在下一次要使用的直接用已经算出的值，避免重复运算，去掉的重复的搜索树

总结

最长不下降子序列

解法一

时间复杂度 o(n^2)

创建数组f[i]表示第i个数据的最长不下降子序列的长度

对每一个输入的数a[i]进行如下操作：

通过遍历找出k，使得f[k]为所有满足 a[k] < a[i] 的值中最大的一个数

如果存在这样的k，那么将a[i]接在a[k]后面可以构成长度为f[k]+1的不下降子序列，因此将f[i]的值更新为f[k]+1

如果不存在这样的k，就说明a[i]之前不存在任何比他小的数，那么就将f[i]的值更新为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package Solution;

public class soll {
	public static void main(String[] args){
		int[] a={13,7,9,16,38,24,37,18,44,19};
		int[] f=new int[10];
		int n=10;
		int big=0;
		for(int i=0;i<n;i++)
		{
			f[i]=1;
			for(int j=0;j<i;j++)
			{
				if(a[j]<a[i]&&f[j]+1>f[i])
				{
					f[i]=f[j]+1;
				}
			}
			big=Math.max(big,f[i]);
		}
	    System.out.println(big);
}
}


数字三角形


原题链接 http://poj.org/problem?id=1163

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;
public class Main {
	public static void main(String[] args){
		int[][] a=new int[100][100];
		int[][] f=new int[100][100];
		Scanner in = new Scanner(System.in);
		int n=in.nextInt();
		for(int i=0;i<n;i++)
			for(int j=0;j<=i;j++)
			a[i][j]=in.nextInt();
		f[0][0]=a[0][0];
		
		for(int i=1;i<n;i++)
		{
			f[i][0]=f[i-1][0]+a[i][0];
			f[i][i]=f[i-1][i-1]+a[i][i];
			
		}
			for(int i=2;i<n;i++)
			for(int j=1;j<i;j++)			
				f[i][j]=Math.max(f[i-1][j-1],f[i-1][j])+a[i][j];
			int max=0; 
			for(int i=0;i<n;i++){
				 if(f[n-1][i]>max)
				 max=f[n-1][i];
			}
        System.out.println(max);
		
}
}

动态规划适用的基本条件

参考链接

https://zhuanlan.zhihu.com/p/25173305

http://www.cnblogs.com/zhangchaoyang/articles/2012070.html