02
—
动态规划相关理论
动态规划的定义
动态规划的英文名称为:dynamic programming,接下来看下《Introduction to algorithms》对动态规划的定义:
A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.
翻译过来:
动态规划算法解决每一个子问题,仅一次,然后保存子问题的结果到内存表中,以此来避免对子问题的重复计算。
两种实现方法
第一种方法符合平常的思维模式,第二种和第一种有点反过来的意思。
03
—
动态规划好在哪里
在上一推送中,给出了一堆括号,其中某个子字符括号串是无效的,然后要求最长有效串。 动态规划:括号知多少
如果采取穷举的方法,时间复杂度会达到 O(n^2),但是这种方法的空间复杂度却为 O(1) 。
为了降低时间复杂度,采取了动态规划算法,使得时间复杂度降为 O(n),还记得为此付出的代价吗?
是的,空间复杂度达到了O(n),与穷举相比。
因此,动态规划法,通过牺牲空间,换来了时间效率,这称作 time-memory trade-off 。
需要弄明白的是,动态规划通过牺牲空间,是如何获得执行效率的呢?
这个问题便是动态规划的核心所在,它将某个子问题的计算结果保存到这个内存表中,为之后的问题提供服务,以此来提升执行效率。
04
—
爬楼梯
今天介绍的这个实际问题,是动态规划比较容易理解的实际应用例子之一,请看下面的问题描述:
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
Note: Given n will be a positive integer.
意思是说,每次你可以爬1个或2个台阶,问爬到第 n 个台阶,一共有多少种不同的方法。
例子1:
- 爬到第2个台阶,共有2种方法,
- 1. 第一步爬1个,第二步爬1个
- 2. 第一步爬2个
例子2:
- 爬到第3个台阶,共有3种方法:
- 1. 第一步,二步,三步分别爬1个
- 2. 第一步爬1个,第二步爬2个
- 3. 第一步爬2个,第二步爬1个
这个问题可以明显分解为一系列子问题,它包括最优解可以被构建,通过子问题的最优解,可以用动态规划解决这个问题。
一个人到达第 i 层楼底包括两种方法:
因此,如果用 dp[i]表示达到第 i 层楼梯的所有方法,那么它进一步等于到达第 i-1 层楼梯的方法加上到达第 i-2 层楼梯的方法的和,即
dp[i] = dp[i-1] + dp[i-2]
有了这个递推公式,自然代码就好写了,如下所示:
public int climbStairs(int n){
if( n==1) return 1;
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
06
—
总结
在爬楼梯这个实际问题中,看到了动态规划的典型特征,用到了O(n)的空间复杂度,记录已经算过的爬到第i-2层和第i-1层的解,然后通过递推公式得到爬到第i层的解。
算法的时间和空间复杂度都为 O(n) 。
来源: https://mp.weixin.qq.com/s?__biz=MzI3NTkyMjA4NA==&mid=2247483837&idx=1&sn=e522c517cb3dc10eff28a5e766af43c9&chksm=eb7c2c76dc0ba56051ec153f57eb36acfb6e76ebd9aa503b1ea415a261fa4369d60679ed9f82#rd