斐波那契數(shù)列
求斐波那契數(shù)列的第 n 項(xiàng)，n <= 39。
- 我對(duì)動(dòng)態(tài)規(guī)劃的理解是，一個(gè)問題的答案可以通過直接得出的結(jié)論來解決。和遞歸不同的是，遞歸注重子問題的解決方式。
動(dòng)態(tài)規(guī)劃注重這個(gè)問題如何通過子問題解決。通常情況下，會(huì)希望不需要額外的存儲(chǔ)空間。最好的情況下，計(jì)算一次用額外空間存儲(chǔ)后，直接輸出答案。 - 要算第三個(gè)數(shù)就是加第一個(gè)數(shù)和第二個(gè)數(shù)
- 要算第四個(gè)數(shù)就是加第二個(gè)數(shù)和第一個(gè)數(shù)
public class Solution {
private int[] fib = new int[40];
public Solution() {
fib[1] = 1;
for (int i = 2; i < fib.length; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
public int Fibonacci(int n) {
return fib[n];
}
}
矩形覆蓋
我們可以用 21 的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問用 n 個(gè) 21 的小矩形無重疊地覆蓋一個(gè) 2n 的大矩形，總共有多少種方法？*
- 當(dāng)n>=3的時(shí)候。第一步有兩種解決思路，先覆蓋一個(gè)2*1，然后再操作?；蛘呦雀采w一個(gè)2*2，然后再操作。所以答案是
f(n-1)+f(n-2)
public int rectCover(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
https://github.com/CyC2018/CS-Notes/blob/master/notes/10.2%20%E7%9F%A9%E5%BD%A2%E8%A6%86%E7%9B%96.md
跳臺(tái)階
一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
- 當(dāng)n>=3的時(shí)候。第一步有兩種解決思路，先跳一階，然后再操作?；蛘咛鴥呻A，然后再操作。
public int JumpFloor(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 2; i < n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
https://github.com/CyC2018/CS-Notes/blob/master/notes/10.3%20%E8%B7%B3%E5%8F%B0%E9%98%B6.md
變態(tài)跳臺(tái)階
一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)... 它也可以跳上 n 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
- 當(dāng)n>=3的時(shí)候。第一步有n中解決方案，第一次跳1級(jí)，第一次跳2級(jí)....第一次跳n級(jí)。所以答案是
f(n)=f(n-1) + f(n-2) + ... + f(0)。 - 思考一下，可以化簡。
f(n-1) = f(n-2) + f(n-3) + ... + f(0)，帶入可得f(n) = 2*f(n-1)
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}
連續(xù)子數(shù)組的最大和
{6, -3, -2, 7, -15, 1, 2, 2}，連續(xù)子數(shù)組的最大和為 8（從第 0 個(gè)開始，到第 3 個(gè)為止）。
- 像數(shù)學(xué)題。
- 先明確2點(diǎn)。第一點(diǎn)：答案是在遍歷數(shù)組的過程中得出來的，有一個(gè)答案，然后不斷的更新，最后得到正確答案。第二點(diǎn)：如果可以的話，只想遍歷一次數(shù)組。
- 動(dòng)態(tài)規(guī)劃注重這個(gè)問題如何通過子問題解決。子問題是：連續(xù)子數(shù)組的最大和，是怎么做的。
- 加，遍歷一個(gè)加一個(gè)，如果比答案大，答案換掉。如果比答案小，不管。
- 如果加的過程中，小于0了。加的結(jié)果換成當(dāng)前的那個(gè)數(shù)，然后再比較。
public int FindGreatestSumOfSubArray(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int greatestSum = Integer.MIN_VALUE;
int sum = 0;
for (int val : nums) {
sum = sum <= 0 ? val : sum + val;
greatestSum = Math.max(greatestSum, sum);
}
return greatestSum;
}
禮物的最大價(jià)值
在一個(gè) mn 的棋盤的每一個(gè)格都放有一個(gè)禮物，每個(gè)禮物都有一定價(jià)值（大于 0）。從左上角開始拿禮物，每次向右或向下移動(dòng)一格，直到右下角結(jié)束。給定一個(gè)棋盤，求拿到禮物的最大價(jià)值。例如，對(duì)于如下棋盤*
- 很熟悉，如果按照之前的算法肯定深度優(yōu)先開始遞歸循環(huán)了。有一個(gè)特點(diǎn)，深度優(yōu)先往往會(huì)有一連串的比較，甚至回溯。動(dòng)態(tài)規(guī)劃會(huì)找一個(gè)數(shù)。這道題里面找的是和。
- 明確兩點(diǎn)。希望遍歷一次數(shù)組，就解決這個(gè)問題。答案在遍歷的過程中得出。
- 從左上角開始遍歷，意味著想走到任意一個(gè)格子，只能從這個(gè)格子的上、左兩個(gè)方向到達(dá)。
public int getMost(int[][] values) {
if (values == null || values.length == 0 || values[0].length == 0)
return 0;
int n = values[0].length;
int[] dp = new int[n];
for (int[] value : values) {
dp[0] += value[0];
for (int i = 1; i < n; i++)
dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];
}
return dp[n - 1];
}
丑數(shù)
把只包含因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）。例如 6、8 都是丑數(shù)，但 14 不是，因?yàn)樗蜃?7。習(xí)慣上我們把 1 當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第 N 個(gè)丑數(shù)。
- 這道題難點(diǎn)根本不在算法。難點(diǎn)在到底什么是丑數(shù)。
- 丑數(shù)是基礎(chǔ)丑數(shù)1，乘數(shù)2、3、5，衍生出來的數(shù)。任意一個(gè)丑數(shù)可以繼續(xù)通過乘上2、3、5，形成新的丑數(shù)。
- 接下來做的事情就是怎么把這些數(shù)按照一定順序不重復(fù)的存儲(chǔ)起來的問題了。
- 最小堆，牛客上面的官方答案。
import java.util.*;
public class Solution {
public int GetUglyNumber_Solution(int index) {
//排除0
if(index == 0)
return 0;
//要乘的因數(shù)
int[] factors = {2, 3, 5};
//去重
HashMap<Long, Integer> mp = new HashMap<>();
//小頂堆
PriorityQueue<Long> pq = new PriorityQueue<>();
//1先進(jìn)去
mp.put(1L, 1);
pq.offer(1L);
long res = 0;
for(int i = 0; i < index; i++){
//每次取最小的
res = pq.poll();
for(int j = 0; j < 3; j++){
//乘上因數(shù)
long next = (long)res * factors[j];
//只取未出現(xiàn)過的
if(!mp.containsKey(next)){
mp.put(next, 1);
pq.offer(next);
}
}
}
return (int)res;
}
}
- 動(dòng)態(tài)規(guī)劃
- 存儲(chǔ)起來，然后輸出。
public int GetUglyNumber_Solution(int N) {
if (N <= 6)
return N;
int i2 = 0, i3 = 0, i5 = 0;
int[] dp = new int[N];
dp[0] = 1;
for (int i = 1; i < N; i++) {
int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
dp[i] = Math.min(next2, Math.min(next3, next5));
if (dp[i] == next2)
i2++;
if (dp[i] == next3)
i3++;
if (dp[i] == next5)
i5++;
}
return dp[N - 1];
}
https://github.com/CyC2018/CS-Notes/blob/master/notes/49.%20%E4%B8%91%E6%95%B0.md
n 個(gè)骰子的點(diǎn)數(shù)
把 n 個(gè)骰子扔在地上，求點(diǎn)數(shù)和為 s 的概率。
- 一個(gè)骰子一個(gè)骰子的扔，提醒一點(diǎn)，就是2個(gè)骰子，骰不出1來。
- 將n-1個(gè)骰子能投出來的數(shù)字的次數(shù)進(jìn)行記錄，即可得到n個(gè)骰子能投出來的數(shù)字的次數(shù)。
- 對(duì)于空間上來說，得到n個(gè)骰子，需要n-1個(gè)骰子的記錄，而n-1個(gè)骰子，需要n-2個(gè)骰子...之前的記錄可以保存這，也可以想辦法清除掉。
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
final int face = 6;
final int pointNum = face * n;
long[][] dp = new long[2][pointNum + 1];
for (int i = 1; i <= face; i++)
dp[0][i] = 1;
int flag = 1; /* 旋轉(zhuǎn)標(biāo)記 */
for (int i = 2; i <= n; i++, flag = 1 - flag) {
for (int j = 0; j <= pointNum; j++)
dp[flag][j] = 0; /* 旋轉(zhuǎn)數(shù)組清零 */
for (int j = i; j <= pointNum; j++)
for (int k = 1; k <= face && k <= j; k++)
dp[flag][j] += dp[1 - flag][j - k];
}
final double totalNum = Math.pow(6, n);
List<Map.Entry<Integer, Double>> ret = new ArrayList<>();
for (int i = n; i <= pointNum; i++)
ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum));
return ret;
}
構(gòu)建乘積數(shù)組
給定一個(gè)數(shù)組 A[0, 1,..., n-1]，請(qǐng)構(gòu)建一個(gè)數(shù)組 B[0, 1,..., n-1]，其中 B 中的元素 B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。要求不能使用除法。
- 屬于是需要存儲(chǔ)空間，但是不能在一次循環(huán)里完成，要兩次循環(huán)。
- 左右兩次遍歷。
public int[] multiply(int[] A) {
int n = A.length;
int[] B = new int[n];
for (int i = 0, product = 1; i < n; product *= A[i], i++) /* 從左往右累乘 */
B[i] = product;
for (int i = n - 1, product = 1; i >= 0; product *= A[i], i--) /* 從右往左累乘 */
B[i] *= product;
return B;
}
