人們認識事物的方法有三種：通過概念（即對事物的基本認識）、通過判斷（即對事物的加深認識）、和推理（對事物的深層認識）。其中，推理又包含歸納法和演繹法。（這些從初中高中一直到大學我們都是一直在學習的，關鍵是理解）

歸納法是從特殊到一般，屬于發(fā)散思維；（如：蘇格拉底會死；張三會死；李四會死；王五會死……，他們都是人。所以，人都會死。）

演繹法是從一般到特殊，屬于匯聚思維。（如：人都會死的；蘇格拉底是人。所以，蘇格拉底會死。）

貪心：

貪心法：是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)值)的一種解題方法。貪心策略總是做出在當前看來是最優(yōu)的選擇，也就是說貪心策略并不是從整體上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)解。（貪心在很多情況下往往是不合適的，所以對于刷題我并不建議使用彈性算法，用動態(tài)規(guī)劃就挺好）

零錢兌換：

給你一個整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個整數(shù) amount ，表示總金額。

計算并返回可以湊成總金額所需的 最少的硬幣個數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回?-1 。

你可以認為每種硬幣的數(shù)量是無限的。

輸入：coins = [1, 2, 5], amount = 11 輸出：3 解釋：11 = 5 + 5 + 1

如果我們用貪心思想，每次取最大的數(shù)額的硬幣，那么6，1，1，1，1，5，5，5湊成10，我們可能可能會陷入一種局部最優(yōu)，但是并不是我們想要的結(jié)果?

public class coinChange {/*** 問題最好硬幣數(shù)組成一個數(shù)* 硬幣面額一定，數(shù)量不一定* f（要組成的面額）=最小組成總數(shù)的硬幣數(shù)量*假設我們知道 F(S) ，即組成金額 S 最少的硬幣數(shù)，最后一枚硬幣的面值是 C*F(S)=F(S?C)+1*那問題就轉(zhuǎn)化成了求F（S-C）* 由于我們不知道c是多少，所以我們要枚舉枚舉每個硬幣面額值，并選擇其中的最小值min（F（S-ci））* @param coins* @param amount* @return*/public int coinChange(int[] coins, int amount) {if(amount == 0) return 0;if(amount<0){return -1;}int[] dp = new int[amount+1];//最多的硬幣情況是全部是1元，共有amount個硬幣.其實這里不一定是+1，+多少都可以。只要dp不可能取都值即可Arrays.fill(dp, amount+1);//必須將所有的dp賦最大值，因為要找最小值dp[0] = 0;//自底向上，金額為0，最小硬幣數(shù)為0。當輸入當金額是0當說話，肯定是0；for(int am = 1; am <= amount; am++) {//自底向上for (int coin : coins) {//遍歷coins的金額if (am >= coin) {//只有總金額大于當前當面值當時候才繼續(xù)dp[am] = Math.min(dp[am], dp[am-coin] + 1);//金額為11的最小硬幣數(shù) 和 金額為(11-一個面值)的最小硬幣數(shù)+1 比較最小值}}}return dp[amount]>amount? -1: dp[amount];//} }

打家劫舍

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
?? ? 偷竊到的最高金額 = 1 + 3 = 4 。
示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。
?? ? 偷竊到的最高金額 = 2 + 9 + 1 = 12 。

/*** 輸入是每個房間的金額* 問題是求能偷到到最大值* 約束是不能偷相鄰的方便* f(0)=0* f(1)=nums[1]* f(2)=max(f(1),f(0)+nums[1])* f(3)=max(f(2),f(1)+nums[2])* f(4)=max(f(3),f(2)+nums[3])* 那么我們可以得出一個轉(zhuǎn)移方程，這個看起來可以用遞歸，但是遞歸會有很多重復計算 不如直接做*/ public class rob {public int rob(int[] nums) {int [] dp=new int[nums.length+1];if(nums==null){return 0;}if (nums.length==1){return nums[0];}dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i <nums.length ; i++) {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[nums.length - 1];} }

做幾道之后發(fā)現(xiàn)動態(tài)規(guī)劃好想還是不是很難哈，但是問題是要怎么識別這是一個動態(tài)規(guī)劃能解決的問題。

來來來再看一道

最長有效括號

給你一個只包含 '('?和 ')'?的字符串，找出最長有效（格式正確且連續(xù)）括號子串的長度。

示例 1：

輸入：s = "(()"
輸出：2
解釋：最長有效括號子串是 "()"
示例 2：

輸入：s = ")()())"
輸出：4
解釋：最長有效括號子串是 "()()"
示例 3：

輸入：s = ""
輸出：0

/*看到這個題目的第一印象，，用棧然后就是我們要保存前面的遍歷結(jié)果。最先想到的當然暴力法，每個都遍歷一邊，比較最大。我壓根沒想到這居然也是一道動態(tài)規(guī)劃的問題*/public int longestValidParentheses(String s) {Deque<Integer> stack = new LinkedList<>();int max = 0;//為了保持一致性，避免邊界條件處理stack.push(-1);for (int i = 0; i < s.length(); i++) {if (s.charAt(i)=='('){//入棧stack.push(i);}else {//出棧stack.pop();if (stack.isEmpty()) {stack.push(i);}else {max =Math.max(max,i-stack.peek());}}}return max;}/** 動態(tài)規(guī)劃解法，雖然這道題我肯定不會有動態(tài)規(guī)劃去解決，因為什么？ 想不到哈哈哈*/ class Solution {public int longestValidParentheses2(String s) {int maxans = 0;int[] dp = new int[s.length()];for (int i = 1; i < s.length(); i++) {if (s.charAt(i) == ')') {if (s.charAt(i - 1) == '(') {dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;}maxans = Math.max(maxans, dp[i]);}}return maxans;} }

剪繩子（同差分整數(shù)）：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長度的 m 段（m、n都是整數(shù)，n>1并且m>1），每段繩子的長度記為 k[0],k[1]...k[m-1] 。請問 k[0]*k[1]*...*k[m-1] 可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18。
?

/*** 一個是j * (i - j) 直接相乘。** 一個是j * dp[i - j]，相當于是拆分(i - j)，對這個拆分不理解的話，可以回想dp數(shù)組的定義。** 那有同學問了，j怎么就不拆分呢？** j是從1開始遍歷，拆分j的情況，在遍歷j的過程中其實都計算過了。那么從1遍歷j，比較(i - j) * j和dp[i - j] * j 取最大的。遞推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));** 也可以這么理解，j * (i - j) 是單純的把整數(shù)拆分為兩個數(shù)相乘，而j * dp[i - j]是拆分成兩個以及兩個以上的個數(shù)相乘。** 如果定義dp[i - j] * dp[j] 也是默認將一個數(shù)強制拆成4份以及4份以上了。** 所以遞推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});** 那么在取最大值的時候，為什么還要比較dp[i]呢？** 因為在遞推公式推導的過程中，每次計算dp[i]，取最大的而已。* @param n* @return*/public int cuttingRope(int n) {int dp[]=new int[n+1];dp[2] =2;for (int i = 2; i <n; i++) {for (int j = 2; j <i; j++) {dp[i] =Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}

總結(jié)

以上是生活随笔為你收集整理的贪心算法和动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。