《演算法筆記》11. 暴力遞歸思維、動態規劃思維
目錄
1 暴力遞歸、動態規劃
轉載註明出處，源碼地址： //github.com/Dairongpeng/algorithm-note ，歡迎star
1.1 暴力遞歸思維
暴力遞歸實質就是嘗試
概念解釋：
回溯-表示大問題被拆解為小問題，小問題返回給大問題資訊，就是回溯
分治：大問題被拆解成小的子問題，就是分治
1、把問題轉化為規模縮小了的同類問題的子問題
2、有明確的不需要繼續進行遞歸的條件（base case）
3、有當得到了子問題的結果之後的決策過程
4、不記錄每個子問題的解（如果記錄每個子問題的解，就是我們熟悉的動態規劃）
1.1.1 暴力遞歸下的嘗試
1.1.1.1 例一：漢諾塔問題
列印n層漢諾塔從最左邊移動到最右邊的全部過程
漢諾塔圓盤移動，如果杆子上沒有圓盤，可以移動到該桿，如果有圓盤則必須移動比該圓盤小的圓盤到該圓盤上
思路1：1. 先想辦法把1到N-1層圓盤移動到中間桿，2. 再把N層的圓盤移動到最右側的桿上 3. 把1到N-1個圓盤從中間桿移動到最右側。結束
思路2：忘掉左中右，理解為從from移動到to，from和to都有可能是左中右。所以定義from，to，other三個杆子。1. 把1到N-1移動到other上。2. 把第N層移動到to上。3. 把1到N層從other移動到to上。結束
思路3：遞歸改非遞歸實現
N層漢諾塔，從左移動到右最優步數是2^N – 1 步。遞歸公式 T(N) = T(N-1) + 1 + T(N-1)。化簡為等比數列，高中數學內容
嘗試是有優劣之分的，譬如思路1和思路二。在動態規劃章節，可以用動態規劃優化我們的嘗試到最優版本
package class11;
import java.util.Stack;
public class Code01_Hanoi {
// 按照思路1的方法
public static void hanoi1(int n) {
leftToRight(n);
}
// 請把1~N層圓盤 從左 -> 右
public static void leftToRight(int n) {
if (n == 1) {
System.out.println("Move 1 from left to right");
return;
}
leftToMid(n - 1);
System.out.println("Move " + n + " from left to right");
midToRight(n - 1);
}
// 請把1~N層圓盤 從左 -> 中
public static void leftToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from left to mid");
return;
}
leftToRight(n - 1);
System.out.println("Move " + n + " from left to mid");
rightToMid(n - 1);
}
public static void rightToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from right to mid");
return;
}
rightToLeft(n - 1);
System.out.println("Move " + n + " from right to mid");
leftToMid(n - 1);
}
public static void midToRight(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to right");
return;
}
midToLeft(n - 1);
System.out.println("Move " + n + " from mid to right");
leftToRight(n - 1);
}
public static void midToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to left");
return;
}
midToRight(n - 1);
System.out.println("Move " + n + " from mid to left");
rightToLeft(n - 1);
}
public static void rightToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from right to left");
return;
}
rightToMid(n - 1);
System.out.println("Move " + n + " from right to left");
midToLeft(n - 1);
}
// 思路二：暴力遞歸 from to other
public static void hanoi2(int n) {
if (n > 0) {
func(n, "left", "right", "mid");
}
}
// 1~i 圓盤 目標是from -> to， other是另外一個
public static void func(int N, String from, String to, String other) {
if (N == 1) { // base
System.out.println("Move 1 from " + from + " to " + to);
} else {
func(N - 1, from, other, to);
System.out.println("Move " + N + " from " + from + " to " + to);
func(N - 1, other, to, from);
}
}
public static class Record {
public boolean finish1;
public int base;
public String from;
public String to;
public String other;
public Record(boolean f1, int b, String f, String t, String o) {
finish1 = false;
base = b;
from = f;
to = t;
other = o;
}
}
// 思路三：非遞歸實現
public static void hanoi3(int N) {
if (N < 1) {
return;
}
Stack<Record> stack = new Stack<>();
stack.add(new Record(false, N, "left", "right", "mid"));
while (!stack.isEmpty()) {
Record cur = stack.pop();
if (cur.base == 1) {
System.out.println("Move 1 from " + cur.from + " to " + cur.to);
if (!stack.isEmpty()) {
stack.peek().finish1 = true;
}
} else {
if (!cur.finish1) {
stack.push(cur);
stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
} else {
System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
}
}
}
}
public static void main(String[] args) {
int n = 3;
hanoi1(n);
System.out.println("============");
hanoi2(n);
System.out.println("============");
hanoi3(n);
}
}
1.1.1.2 例二：字元串子序列問題
1、列印一個字元串的全部子序列
子串：必須是連續的，用for循環就行
子序列：比子串自由，在原始序列的基礎上，以此拿字元但是可以不連續
- 見process1方法程式碼
2、列印一個字元串的全部子序列，要求不要出現重複字面值的子序列
比如aaabcccc就會得到很多相同字面值的子序列，我們把重複字面值的子序列只要一個
- 見process2方法程式碼
package class11;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
public class Code02_PrintAllSubsquences {
public static List<String> subs(String s) {
char[] str = s.toCharArray();
String path = "";
List<String> ans = new ArrayList<>();
process1(str, 0, ans, path);
return ans;
}
// str固定，不變
// index此時來到的位置, 要 or 不要
// 如果index來到了str中的終止位置，把沿途路徑所形成的答案，放入ans中
// 之前做出的選擇，就是沿途路徑path
public static void process1(char[] str, int index, List<String> ans, String path) {
if (index == str.length) {
ans.add(path);
return;
}
String no = path;
process1(str, index + 1, ans, no);
String yes = path + String.valueOf(str[index]);
process1(str, index + 1, ans, yes);
}
public static List<String> subsNoRepeat(String s) {
char[] str = s.toCharArray();
String path = "";
HashSet<String> set = new HashSet<>();
process2(str, 0, set, path);
List<String> ans = new ArrayList<>();
for (String cur : set) {
ans.add(cur);
}
return ans;
}
// str index 用set去重
public static void process2(char[] str, int index,
HashSet<String> set, String path) {
if (index == str.length) {
set.add(path);
return;
}
String no = path;
process2(str, index + 1, set, no);
String yes = path + String.valueOf(str[index]);
process2(str, index + 1, set, yes);
}
public static void main(String[] args) {
String test = "aacc";
List<String> ans1 = subs(test);
List<String> ans2 = subsNoRepeat(test);
for (String str : ans1) {
System.out.println(str);
}
System.out.println("=================");
for (String str : ans2) {
System.out.println(str);
}
System.out.println("=================");
}
}
1.1.1.3 例四：字元串全排列問題
1、列印一個字元串的全部排列,process
2、列印一個字元串的全部排列，要求不要出現重複的排列.process2。方法1，可以用HashSet最後去重，該方式是把遞歸的所有結果進行篩選。方法2可以拋棄重複元素，例如a在0位置已經嘗試完畢，再有一個元素也是a要到0位置，那麼禁止，該方法是遞歸的時候事先判斷要不要進行下一步遞歸，更快一點。該方法又叫分支限界
package class11;
import java.util.ArrayList;
import java.util.List;
public class Code03_PrintAllPermutations {
public static ArrayList<String> permutation(String str) {
ArrayList<String> res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
process(chs, 0, res);
return res;
}
// str[0..i-1]已經做好決定的
// str[i...]都有機會來到i位置
// i到達終止位置，str當前的樣子，就是一種結果 -> ans
public static void process(char[] str, int i, ArrayList<String> ans) {
// i來到終點，返回該種答案
if (i == str.length) {
ans.add(String.valueOf(str));
}
// 如果i沒有終止，i... 都可以來到i位置
for (int j = i; j < str.length; j++) { // i後面所有的字元都有機會來到i位置
swap(str, i, j);
process(str, i + 1, ans);
// 恢復交換之前的現場
swap(str, i, j);
}
}
public static ArrayList<String> permutationNoRepeat(String str) {
ArrayList<String> res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
process2(chs, 0, res);
return res;
}
// str[0..i-1]已經做好決定的
// str[i...]都有機會來到i位置
// i終止位置，str當前的樣子，就是一種結果 -> ans
public static void process2(char[] str, int i, ArrayList<String> res) {
if (i == str.length) {
res.add(String.valueOf(str));
return;
}
boolean[] visit = new boolean[26]; // visit[0 1 .. 25] 代表a-z的字元有沒有在當前出現過
// i右邊的字元都有機會
for (int j = i; j < str.length; j++) {
// str[j] = 'a' -> 0 visit[0] -> 'a'
// str[j] = 'z' -> 25 visit[25] -> 'z'
// 如果沒出現過就沒有機會
if (!visit[str[j] - 'a']) {
visit[str[j] - 'a'] = true;
swap(str, i, j);
process2(str, i + 1, res);
swap(str, i, j);
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
String s = "aac";
List<String> ans1 = permutation(s);
for (String str : ans1) {
System.out.println(str);
}
System.out.println("=======");
List<String> ans2 = permutationNoRepeat(s);
for (String str : ans2) {
System.out.println(str);
}
}
}
1.1.1.4 例六：用遞歸逆序一個棧(考驗腦迴路)
給你一個棧，請你逆序這個棧，不能申請額外的數據結構，只能使用遞歸函數。如何實現？
思路，先不要想著逆序它，實現一個f函數，f函數的作用是把棧傳進去，想辦法拿到棧低元素並返回。
package class11;
import java.util.Stack;
public class Code04_ReverseStackUsingRecursive {
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
// i是棧底元素，f調整之後的棧成為去掉棧底元素後的棧
int i = f(stack);
// 遞歸調用
reverse(stack);
// 經過base case之後，棧為空，此時壓入的就是當前的棧底
stack.push(i);
}
public static int f(Stack<Integer> stack) {
// 彈出棧頂，用result臨時變數記住這個棧頂元素
int result = stack.pop();
// 如果棧為空，向上返回彈出的result，此時result就是棧底元素
if (stack.isEmpty()) {
return result;
} else {
// 此時棧不為空，讓子問題給我一個臨時變數，臨時變數就是子問題base case返回的result
int last = f(stack);
// 把我彈出的result再壓入棧，向上返回子問題給我的result
stack.push(result);
return last;
}
}
public static void main(String[] args) {
Stack<Integer> test = new Stack<Integer>();
test.push(1);
test.push(2);
test.push(3);
test.push(4);
test.push(5);
reverse(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
}
}
1.2 動態規劃模型
1.2.1 從左往右嘗試模型
1.2.1.1 數字字元轉化問題
註：facebook面試題
1、規定1和A對應，2和B對應，3和C對應…。那麼一個數字字元比如”111″就可以轉化為：”AAA”,”KA”,”AK”。
給定一個只有數字字元組成的字元串str,返回有多少種轉化結果
思路：根據從左往右，我們劃分多大，來嘗試，比如111，我們嘗試一個1，為”A”,剩下兩個1去繼續嘗試。如果我們兩個1嘗試，就是”K”。三個1超過26字元，無法嘗試。繼續如此周而復始
package class11;
public class Code06_ConvertToLetterString {
public static int number(String str) {
if (str == null || str.length() == 0) {
return 0;
}
// i初始為0，表示0位置往後有多少中轉化結果
return process(str.toCharArray(), 0);
}
// str[0...i-1]已經轉化完了，固定了
// i之前的位置，如何轉化已經做過決定了, 不用再關心
// i... 有多少種轉化的結果
public static int process(char[] str, int i) {
// i和字元串長度一樣大，右側沒有字元了。找到1中轉化是0~n-1位置的轉化
if (i == str.length) { // base case
return 1;
}
// i之前的決策，讓當前i位置單獨面對一個0字元，那麼之前決策錯誤，返回0
// 例如10先轉化為A，2位置是0字元無法轉化，當前決策無效
// 而10直接轉化為J,直接到終止位置，返回一種轉化J
if (str[i] == '0') {
return 0;
}
// i位置如果是1或者2，有可能和下一個位置共同轉化，因為字元數為0~26
// 反之3~9超過26不需要決策
// str[i] 如果是1，總是有兩個選擇，因為最大為19，不超過26
if (str[i] == '1') {
int res = process(str, i + 1);
if (i + 1 < str.length) {
res += process(str, i + 2);
}
return res;
}
// str[i] 如果是2，那麼有可能有兩種選擇，需要看是否朝貢國26
if (str[i] == '2') {
int res = process(str, i + 1);
if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
res += process(str, i + 2); // (i和i+1)作為單獨的部分，後續有多少種方法
}
return res;
}
// str[i] 在3~9的位置，下個位置必須決策一種選擇
return process(str, i + 1);
}
public static int dpWays2(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[] dp = new int[N+1];
dp[N] = 1;
for(int i = N-1; i >= 0; i--) {
if (str[i] == '0') {
dp[i] = 0;
}
if (str[i] == '1') {
dp[i] = dp[i + 1];
if (i + 1 < str.length) {
dp[i] += dp[i + 2];
}
}
if (str[i] == '2') {
dp[i] = dp[i + 1];
if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
dp[i] += dp[i + 2]; // (i和i+1)作為單獨的部分，後續有多少種方法
}
}
}
return dp[0];
}
public static int dpWays(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[] dp = new int[N + 1];
dp[N] = 1;
for (int i = N - 1; i >= 0; i--) {
if (str[i] == '0') {
dp[i] = 0;
} else if (str[i] == '1') {
dp[i] = dp[i + 1];
if (i + 1 < N) {
dp[i] += dp[i + 2];
}
} else if (str[i] == '2') {
dp[i] = dp[i + 1];
if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
dp[i] += dp[i + 2];
}
} else {
dp[i] = dp[i + 1];
}
}
return dp[0];
}
public static void main(String[] args) {
System.out.println(number("11111"));
System.out.println(dpWays2("11111"));
}
}
1.2.1.2 背包價值問題
2、給定兩個長度都為N的數組weights和values，weight[i]和values[i]分別代表i號物品的重量和價值。
給定一個正數bag，表示一個載重bag的袋子，你裝的物品不能超過這個重量。返回你能裝下最多的價值是多少？
package class11;
public class Code07_Knapsack {
public static int getMaxValue(int[] w, int[] v, int bag) {
return process(w, v, 0, 0, bag);
}
// 第一種嘗試
// 不變 ： w[] 重量數組 v[] 價值數組 bag 袋子的總載重
// index... 最大價值
// 0..index-1上做了貨物的選擇，使得你已經達到的重量是多少 alreadyW
// 如果返回-1，認為沒有方案
// 如果不返回-1，認為返回的值是真實價值
public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
// base case
if (alreadyW > bag) {
return -1;
}
// 重量沒超
if (index == w.length) {
return 0;
}
// 當前不選擇index的貨物情況下，後續的價值
// 無需傳遞當前index的重量，且p1就是總價值
int p1 = process(w, v, index + 1, alreadyW, bag);
// 當前選擇了index的貨物，把重量加上，繼續向下遞歸
int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
// p2表示要了當前貨物之後總價值應該是後續價值加上當前價值
int p2 = -1;
if (p2next != -1) {
p2 = v[index] + p2next;
}
return Math.max(p1, p2);
}
public static int maxValue(int[] w, int[] v, int bag) {
return process(w, v, 0, bag);
}
// 第二種嘗試。更經典
// 只剩下rest的空間了，
// index...貨物自由選擇，但是剩餘空間不要小於0
// 返回 index...貨物能夠獲得的最大價值
public static int process(int[] w, int[] v, int index, int rest) {
// base case 1 無效方案
if (rest < 0) {
return -1;
}
// rest >=0。index來到終止位置，當前返回0價值
// base case 2
if (index == w.length) {
return 0;
}
// 有貨也有空間。當前index不選擇，得到p1總價值
int p1 = process(w, v, index + 1, rest);
int p2 = -1;、
// 選擇了index位置，剩餘空間減去當前重量
int p2Next = process(w, v, index + 1, rest - w[index]);
// 選擇index的總價值，是index...的價值加上個當前index的價值
if(p2Next!=-1) {
p2 = v[index] + p2Next;
}
return Math.max(p1, p2);
}
public static int dpWay(int[] w, int[] v, int bag) {
int N = w.length;
int[][] dp = new int[N + 1][bag + 1];
for (int index = N - 1; index >= 0; index--) {
for (int rest = 1; rest <= bag; rest++) {
dp[index][rest] = dp[index + 1][rest];
if (rest >= w[index]) {
dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
}
}
}
return dp[0][bag];
}
public static void main(String[] args) {
int[] weights = { 3, 2, 4, 7 };
int[] values = { 5, 6, 3, 19 };
int bag = 11;
System.out.println(maxValue(weights, values, bag));
System.out.println(dpWay(weights, values, bag));
}
}
1.2.2 範圍上的嘗試模型
1.2.2.1 玩家抽取紙牌問題
給定一個整形數組arr，代表數值不同的紙牌排成一條線，玩家A和玩家B依次拿走每張紙牌。規定玩家A先拿，玩家B後拿，但是每個玩家每次只能拿走最左或最右的紙牌，玩家A和玩家B都絕頂聰明。請趕回最後獲勝者的分數
絕頂聰明學術上的解釋：雙方玩家都會使得對方玩家在當前單獨改變策略時，不會獲得更大的收益。
package class11;
public class Code08_CardsInLine {
// 主函數
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
// 先手在0~length-1和後手在0~length-1上，誰分數大就是獲勝者的分數
return Math.max(
f(arr, 0, arr.length - 1),
s(arr, 0, arr.length - 1)
);
}
// L....R 先手函數
// F S L+1..R
// L..R-1
public static int f(int[] arr, int L, int R) {
// base case 當只剩一張牌，且是先手
if (L == R) {
return arr[L];
}
// 當前是先手，選擇最好的
return Math.max(
arr[L] + s(arr, L + 1, R),
arr[R] + s(arr, L, R - 1)
);
}
// 後手函數
// arr[L..R]
public static int s(int[] arr, int L, int R) {
// base case 當只剩一張牌，且為後手
if (L == R) {
return 0;
}
// 當前是後手，好的被絕頂聰明的先手選走了
// 相當於是先手的決策剩下的當前牌，留下最差的min
return Math.min(
f(arr, L + 1, R), // 對手挑了 arr[i]
f(arr, L, R - 1) // 對手挑了 arr[j]
);
}
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] f = new int[N][N];
int[][] s = new int[N][N];
for(int i = 0; i < N;i++) {
f[i][i] = arr[i];
}
// s[i][i] = 0;
for(int i = 1; i < N;i++) {
int L =0;
int R =i;
while(L < N && R < N) {
f[L][R] = Math.max(
arr[L] + s[L + 1][ R],
arr[R] + s[L][R - 1]
);
s[L][R] = Math.min(
f[L + 1][R], // arr[i]
f[L][R - 1] // arr[j]
);
L++;
R++;
}
}
return Math.max(f[0][N-1], s[0][N-1]);
}
public static void main(String[] args) {
int[] arr = { 4,7,9,5,19,29,80,4 };
// A 4 9
// B 7 5
System.out.println(win1(arr));
System.out.println(win2(arr));
}
}
1.2.2.2 N皇后問題
N皇后問題是指在N*N的棋盤上要擺N個皇后，要求任何兩個皇后不同行，不同列，也不在同一條斜線上。
給定一個整數n，返回n皇后的擺法有多少種。
n=1，返回1
n=2或3,2皇后和3皇后問題無論怎麼擺都不行，返回0
n=8，返回92
最優的N皇后的嘗試方法，時間複雜度為N^N，但是process2是用位運算加速了常數項的時間
package class11;
public class Code09_NQueens {
public static int num1(int n) {
if (n < 1) {
return 0;
}
// record[0] ? record[1] ? record[2]
// record[i] -> i行的皇后，放在了第幾列
int[] record = new int[n];
return process1(0, record, n);
}
// 潛台詞：record[0..i-1]的皇后，任何兩個皇后一定都不共行、不共列，不共斜線
// 目前來到了第i行，在i行準備放皇后
// record[0..i-1]表示之前的行，放了的皇后位置
// n代表整體一共有多少行 0~n-1行
// 返回值是，擺完所有的皇后，合理的擺法有多少種
// 嘗試過程
public static int process1(int i, int[] record, int n) {
if (i == n) { // 終止行
return 1;
}
// 沒有到終止位置，還有皇后要擺
int res = 0;
// 當前行在i行，嘗試i行所有的列 -> j
for (int j = 0; j < n; j++) {
// 當前i行的皇后，放在j列，會不會和之前(0..i-1)的皇后，不共行共列共斜線，
// 如果是，認為有效，當前可以擺在j列的位置
// 如果不是，認為無效
if (isValid(record, i, j)) {
// 當前存在i行的有效值為j列位置
record[i] = j;
res += process1(i + 1, record, n);
}
}
return res;
}
// record[0..i-1]你需要看，record[i...]不需要看
// 返回i行皇后，放在了j列，是否有效
// a行b列的皇后，和c行d列的皇后會不會衝突，coding的條件是不共行
// 共列的話b==d，共斜線的話|a-c|==|b-d|
public static boolean isValid(int[] record, int i, int j) {
// 之前的某個k行的皇后
for (int k = 0; k < i; k++) {
// k, record[k] i, j
if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
return false;
}
}
return true;
}
// 請不要超過32皇后問題
public static int num2(int n) {
if (n < 1 || n > 32) {
return 0;
}
// 如果你是13皇后問題，limit 最右13個1，其他都是0
int limit = n == 32 ? -1 : (1 << n) - 1;
return process2(limit, 0, 0, 0);
}
// limit 劃定了問題的規模 -> 固定
// 用位運算加速常數項時間
// colLim 列的限制，1的位置不能放皇后，0的位置可以
// leftDiaLim 左斜線的限制，1的位置不能放皇后，0的位置可以
// rightDiaLim 右斜線的限制，1的位置不能放皇后，0的位置可以
public static int process2(
int limit,
int colLim,
int leftDiaLim,
int rightDiaLim) {
if (colLim == limit) { // base case
return 1;
}
// 所有可以放皇后的位置，都在pos上
// colLim | leftDiaLim | rightDiaLim -> 總限制
// ~ (colLim | leftDiaLim | rightDiaLim) -> 左側的一坨0干擾，右側每個1，可嘗試
// 把左側的去反後的一坨1，移除掉
int pos = limit & ( ~(colLim | leftDiaLim | rightDiaLim) );
int mostRightOne = 0;
int res = 0;
while (pos != 0) {
// 提取出pos中，最右側的1來，剩下位置都是0
mostRightOne = pos & (~pos + 1);
pos = pos - mostRightOne;
res += process2(limit,
colLim | mostRightOne,
(leftDiaLim | mostRightOne) << 1,
(rightDiaLim | mostRightOne) >>> 1);
}
return res;
}
public static void main(String[] args) {
int n = 15;
long start = System.currentTimeMillis();
System.out.println(num2(n));
long end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
start = System.currentTimeMillis();
System.out.println(num1(n));
end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
}
}
如何嘗試一件事？
1、有經驗但是沒有方法論
2、怎麼判斷一個嘗試
3、難道嘗試這件事真的只能拼天賦么，該怎麼搞定面試？
4、動態規劃是啥？好高端的樣子，和嘗試有什麼關係？
請見下一章，暴力遞歸到動態規劃的轉移套路，解決面試中動態規劃的問題。
