什么是動(dòng)態(tài)規(guī)劃
按照定義锌订，動(dòng)態(tài)規(guī)劃是把一個(gè)大問題拆解成一堆小問題，但是這個(gè)不是動(dòng)態(tài)規(guī)劃的核心思想辈双。而取決于該問題是否能用動(dòng)態(tài)規(guī)劃解決的是這些"小問題“會(huì)不會(huì)被被重復(fù)調(diào)用聚请。舉一個(gè)例子“1+1+1+1=4”，如果在左側(cè)在“+1”呢砍鸠？你不會(huì)把右側(cè)的4個(gè)“+1”重新算一遍扩氢，而是直接得出結(jié)論“1+4”。
題目特點(diǎn)
- 計(jì)數(shù)
- 有多少種方式走到右下角
- 有多少種方法選出k個(gè)數(shù)使得和是Sum
- 求最大最小值
- 從左上角到右下角路徑的最大數(shù)字和
- 最長上升子序列長度
- 求存在性
- 取石頭游戲爷辱，先手是否必勝
- 能不能選出k個(gè)數(shù)使得和是Sum
問題1
你有三種硬幣录豺，分別面值2元,5元和7元，每種硬幣都有足夠多饭弓，買一本書需要27元双饥，如何用最少的硬幣組合正好付清，不需要對(duì)方找錢弟断。
我們不關(guān)心前面的K-1枚硬幣是怎么拼出27-ak的(可能有1種拼法,可能 有100種拼法),而且我們現(xiàn)在甚至還不知道ax和K,但是我們確定前面的硬幣拼出了27-ak咏花。
如果ak是2,f(27)應(yīng)該是f(27-2)+1(加上最后這一枚硬幣2) ;
如果ak是5,(27)應(yīng)該是f(27-5)+1(加上最后這一枚硬幣5) ;
如果ak是7,f(27)應(yīng)該是(27-7)+1(加上最后這一枚硬幣7);
最后問題抽象為f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}。
如果x-2阀趴，x-5昏翰，x-7小于0怎么辦？我們規(guī)定這些拼不出來的都為最大值刘急。所以有f[1]=min{f[-1]+1,f[-4]+1,f[-4]+1} = 最大值棚菊，它是拼不出來的。
最后附上代碼：
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().coinChange(new int[]{2, 5, 7}, 27));
}
public int coinChange(int[] array, int m) {
int length = array.length;
// f[mounts] 代表mounts元下排霉，使用的最少硬幣數(shù)量
int[] f = new int[m + 1];
// 初始化
f[0] = 0;
for (int mounts = 1; mounts <= m; mounts++) {
f[mounts] = Integer.MAX_VALUE;
// 遍歷硬幣的種類
for (int j = 0; j < length; j++) {
// 如果mounts比
if (mounts >= array[j] && f[mounts - array[j]] != Integer.MAX_VALUE) {
f[mounts] = Math.min(f[mounts], f[mounts - array[j]] + 1);
}
}
}
if (f[m] == Integer.MAX_VALUE) return -1;
return f[m];
}
}
動(dòng)態(tài)規(guī)劃步驟
- 確定狀態(tài)
- 轉(zhuǎn)移方程
- 初始條件和邊界情況
- 計(jì)算順序
問題2
給定m行n列的網(wǎng)格,有一個(gè)機(jī)器人從左上角(00)出發(fā),每一步可以向下
或者向右走一步窍株，問有多少種不同的方式走到右下角民轴。
我們按照前面的動(dòng)態(tài)規(guī)劃步驟來寫思路。
- 確定狀態(tài)
最后一步:無論機(jī)器人用何種方式到達(dá)右下角,總有最后挪動(dòng)的一步向右或者向下球订，右下角坐標(biāo)設(shè)為(m-1,n-1)后裸，那么前一步機(jī)器人一定是在(m-2,n-1)或者(m-1,n-2)。狀態(tài):設(shè)f[i][j]為機(jī)器人有多少種方式從左上角走到(i,j)冒滩。 - 轉(zhuǎn)移方程
f[i][j] = f[i-1][j] + f[i][j-1] - 初始條件和邊界情況
初始條件：f[0][0] = 1
邊界情況：i=0或j=0微驶，則前一步只能有一個(gè)方向過來，即f[0][j] = 1, f[i][0] = 1 -
計(jì)算順序
因?yàn)槲覀兠看味家玫阶筮吅蜕线呉粋€(gè)格子的值开睡，所以先遍歷行因苹，后遍歷列。
由此這個(gè)問題就分析完了篇恒，下面是完整代碼：
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().uniquePaths(4, 8));
}
public int uniquePaths(int m, int n) {
int[][] f = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
f[i][j] = 1;
continue;
}
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
}
問題3
有n塊石頭分別在x軸的0,1,...,n-1的位置一只青蛙在石頭0,想跳到石頭n-1扶檐。如果青蛙在第i塊石頭上,它最多可以向右跳距離ai，問青蛙能否跳到石頭n-1胁艰。
例子：
輸入:a=[2,3,1,1,4] 輸出:True
輸入:a=[3,2,1,0,4] 輸出:False
確定狀態(tài)
最后一步:如果青蛙能跳到最后一塊石頭n-1,我們考慮它跳的最后一步款筑。這一步是從石頭i跳過來,i<n-1。這需要兩個(gè)條件同時(shí)滿足1.青蛙可以跳到石頭腾么；2.最后一步不超過跳躍的最大距離:n-1-i<=a奈梳。設(shè)f[i]表示青蛙能不能跳到石頭i。-
轉(zhuǎn)移方程
f[i] = OR(f[j] && a[j] + j >= i)
初始條件和邊界情況
f[0] = True計(jì)算順序
按順序分別計(jì)算 f[1],...,f[n-1]
以下是完整代碼：
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().canJump(new int[]{3, 2, 1, 0, 4}));
}
public boolean canJump(int[] a) {
boolean[] f = new boolean[a.length];
f[0] = true;
for (int i = 1; i < a.length; i++) {
f[i] = false;
for (int j = 0; j < i; j++) {
if (f[j] && a[j] + j >= i) {
f[i] = true;
break;
}
}
}
return f[a.length - 1];
}
}
問題4
最大乘積子序列：給定a[0],...,a[n-1],找到最長的連續(xù)子序列i,i+1,i+2,i+j,使得a[i] * ... * a[j]最大
例子：
輸入:[2,3,-2,4]
輸出:6(子序列[2,3]:2*3=6)
確定狀態(tài)
有最大子序列的最后一個(gè)元素a[j]解虱，第一種情況攘须，最大為a[j]本身;第二種情況，如果a[j]大于0殴泰，我們希望a[j-1]結(jié)尾的最大子序列最大于宙，如果a[j]小于0，則反之艰匙。
所以問題的關(guān)鍵是我們需要同時(shí)保留最大值和最小值限煞。狀態(tài):f[i]=以a[j]結(jié)尾的連續(xù)子序列的最大乘積,設(shè)g[j]=以a[j]結(jié)尾的連續(xù)子序列的最小乘積。轉(zhuǎn)移方程
這里有個(gè)小技巧员凝，我們其實(shí)可以不管是否大于0的問題署驻。
f[j] = Math.max(a[j], Math.max(a[j] * f[j-1], a[j] * g(j-1)))
g[j] = Math.min(a[j], Math.min(a[j] * f[j-1], a[j] * g(j-1)))初始條件和邊界情況
無計(jì)算順序
f[0], g[0], f[1], g[1], f[2], g[2],..., f[n-1], g[n-1]
以下是完整代碼：
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().maxSubArray(new int[]{2, 3, -2, 4}));
}
public int maxSubArray(int[] a) {
int[] f = new int[a.length];
int[] g = new int[a.length];
int result = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
f[i] = a[i];
if (i > 0) {
f[i] = Math.max(a[i], Math.max(f[i - 1] * a[i], g[i - 1] * a[i]));
}
if (f[i] > result) {
result = f[i];
}
g[i] = a[i];
if (i > 0) {
g[i] = Math.min(a[i], Math.min(f[i - 1] * a[i], g[i - 1] * a[i]));
}
}
return result;
}
}
問題5
有n個(gè)階梯，一個(gè)人每一步只能跨一個(gè)臺(tái)階或是兩個(gè)臺(tái)階健霹，問這個(gè)人一共有多少種走法旺上？
確定狀態(tài)
f[n]是到第n級(jí)臺(tái)階有幾種走法轉(zhuǎn)移方程
到第n級(jí)臺(tái)階只有兩種可能，從第n-1上來糖埋，從n-2上來宣吱。
f[n] = f[n-1] + f[n-2]初始條件和邊界情況
f[0] = 1
f[1] = 1計(jì)算順序
無
以下是完整代碼
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().climbStairs(3));
}
public int climbStairs(int n) {
int[] f = new int[n + 1];
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
}
問題6
給定數(shù)量不限的硬幣，幣值為25分瞳别、10分征候、5分和1分杭攻，編寫代碼計(jì)算n分有幾種表示法。(結(jié)果可能會(huì)很大疤坝，你需要將結(jié)果模上1000000007)
示例1:
輸入: n = 5
輸出：2
解釋: 有兩種方式可以湊成總金額:
5=5
5=1+1+1+1+1
示例2:
輸入: n = 10
輸出：4
解釋: 有四種方式可以湊成總金額:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
有以下的思路
/*
f(k, n) = f(k-1, n) 前 k-1 個(gè)硬幣組成 n - COIN * 0 分的情況（第 k 個(gè)硬幣使用 0 個(gè)）
+ f(k-1, n-COIN) 前 k-1 個(gè)硬幣組成 n - COIN * 1 分的情況（第 k 個(gè)硬幣使用 1 個(gè)）
+ f(k-1, n-COIN*2) 前 k-1 個(gè)硬幣組成 n - COIN * 2 分的情況（第 k 個(gè)硬幣使用 2 個(gè)）
+ ... ...
+ f(k-1, n-COIN*i) 前 k-1 個(gè)硬幣組成 n - COIN * i 分的情況（第 k 個(gè)硬幣使用 i 個(gè)）
當(dāng) n - COIN*i < 0 時(shí)循環(huán)停止兆解。
*/
以下代碼就是上述思路的體現(xiàn)，但是在leecode中會(huì)超時(shí)
class Solution {
static int[] coins = new int[]{0, 1, 5, 10, 25};
// 前k個(gè)硬幣組成n分有幾種情況跑揉？
public static int f(int k, int n) {
if (k == 1) {
return 1;
}
int currentCoin = coins[k];
int result = 0;
for (int i = 0; n - currentCoin * i >= 0; i++) {
result += f(k - 1, n - currentCoin * i);
}
return result;
}
public int waysToChange(int n) {
return f(4, n);
}
}
