11601 Week 6 - Dynamic Programming

作者 QIFAN 日期 2016-10-11
11601 Week 6 - Dynamic Programming

CMU 11601 Coding BootCamp


本周动态规划

知识点

In Class Practice

用recursion算斐波那契数列
及简单的java继承题

Homework

Part 1

Q1. When a function recursively calls itself as its very last action, we refer to that as a:

  • simple recursive call
  • tail call
  • base case
  • none of the above

Q2. Dynamic Burglary
与LeetCode 198 House Robber 一样。

Part 2

  1. Coin on the Table Redux
    Coin on the Table 的变种。只要搞清楚了每一个步是由上方,左方或者右方来,所以只要取三者最小值。要注意的一点就是与原版不同,对于每一种方向,每一行的cost要单独走一遍。所以在每一行要进行三次遍历,顺序应该为从上,从左,从右的顺序。做了这么多题觉得DP还是有进步的。

Shuffle

Interviewer

Question 1: cc 8.6
Towers of Hanoi
概括出移动的过程,使用递归

Question 2: cc 6.8
有个一百层的楼,你有俩鸡蛋。当鸡蛋从N层及以上摔下,就会摔烂,若从N层以下扔下,则不会破。求在最差情况下的最小扔鸡蛋次数。
答案没看懂。

Question 3: cc 3.3
建一个数据结构SetOfStacks来模拟放盘子的过程。当某个stack超过一定数量,则新建一个stack来放盘子,其push与pop应该与单stack一样。

Interviewee

本周两道Brain Tease题,一道DP题
Q1. 有一百个关着的柜子,有个小盆友手痒。她在第一次开启了所有柜子,第二次关闭了所有偶数位的柜子,第三次及以后改变能被i整除的柜子(i为次数,改变指的是若该柜子为关上则打开,若为打开则关上)。
问100次操作以后,有多少开着的柜子。
答:基本思想:

  • 发现某一位置柜子开合的次数就是它的约数的个数。so tricky!
  • 偶数个约数则开着,奇数个约束则关着。
  • 怎么算约数个数呢?是不是想到写一个function呀!

  • 拥有整数平方根的数的总约数都为奇数,其他的都是偶数!(自个想为啥)
    So, 10个开着,90个关着

Q2. 初中求概率题 = =

Q3. 有个N*M的boolean矩阵,每个格子true代表可以走,false代表不能走,小明从左上角(0, 0)出发,问能否走到右下角(N-1, M-1)

答:本来是可以用DP做的,而我深爱着algorithm,因为实在和Percolation太像了,就又用了union find。另建一个int矩阵,若左方或右方有true格子,就将这个位置的值和那个格子一样,最后如果(0, 0)的值与(N-1, M-1)的root一样,则说明有路径可走。
*root:因为路径的方向不确定,所以不能保证连接的格子的值始终为起点值,但肯定可以追寻到最开始的起点,(N-1, M-1)的值的起点为(0, 0)`则为连通。

public boolean existPath(boolean[] metrix) {
if(metrix == null || metrix.length == 0 || !metrix[0][0]) return false;
int N = metrix.length;
int M = metrix[0].length;
int[] board = new int[N * M];
board[0] = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
checkPath(metrix, board, i, j);
}
}
return board[0][0] == root(N * M - 1, board);
}
private void checkPath(boolean[][] metrix, int[] board, int i, int j) {
if(!metrix[i][j]) return;
if(i > 0 && metrix[i-1][j]) {
board[i * M + j] = board[(i - 1) * M + j];
return;
}
if(j > 0 && metrix[i][j-1]) {
board[i * M + j] = board[i * M + j - 1];
return;
}
if(i < N - 1 && metrix[i+1][j]) {
board[i * M + j] = board[(i+1) * M + j];
return;
}
if(j < M - 1 && metrix[i][j+1]) {
board[i * M + j] = board[i * M + j + 1];
return;
}
}
private int root(int n, int[] board) {
while (board[n] != n + 1) {
n = board[n];
}
return n;
}