動態規劃：這種算法思想多用來求解最優化問題，因此這里存在一個最優化法則，法則指出最優化問題任一實例的最優解，都是由其子實例的最優解構成的。一般來說，自底向上的動態規劃更容易設計，但是帶有記憶功能的自頂向下的動態規劃跟能高效的解決問題（尤其是針對重疊子的問題）。

1、幣值最大化問題：給定一排n枚硬幣，面值為正整數c1，c2，...，cn,面值可能相同，請問如何選取硬幣，可以使得在其原始位置不相鄰的條件下。所選幣值總和最大。

思路：我們可以將問題劃分為取最后一枚硬幣和不取最后一枚硬幣。根據不相鄰這一條件，若取最后一枚硬幣，則我們繼續判斷前n-2枚硬幣中的幣值總和最大問題；若不取最后一枚，則我們繼續判斷前n-1枚硬幣中的幣值總和最大問題。

由此得到遞推方程如下，并且我們已知F(0) = 0，F(1) = c1,

Input:

6

5 1 2 10 6 2

Output:

17

?

import java.util.Scanner;public class Main {static int[] c = new int[10];static int[] f = new int[10];static Scanner in = new Scanner(System.in);public static void main(String[] args) {int n = in.nextInt();for (int i = 1; i <= n; i++) {c[i] = in.nextInt();}System.out.println(coinRow(n));}private static int coinRow(int n) {f[0] = 0;f[1] = c[1];for (int i = 2; i <= n; i++) {f[i] = Math.max(c[i] + f[i-2], f[i-1]);}return f[n];} }

我們在這個過程中不僅得出了最大金額為17，我們在f[]中也可以求得前i枚硬幣（1<=i<=6）的最大金額。時間復雜度和空間復雜度均為O(n)。

?

2、找零問題：假設我們需要找零的金額為n，至少需要多少面值為d1<d2<...<dm的硬幣？其中d1 = 1，且每種面值的硬幣無限制。

思路：我們可以理解獲得n的途徑為：在總金額為n-dj的一堆硬幣中在找一枚面值為dj的硬幣，其中j=1,2，...,m，且n>=dj。因此找到一個滿足要求的dj使得F(n-dj) + 1最小的dj即可。由于1是常量，所以我們需要專注尋找一個最小的F(d-dj)。

由此得到的遞推公式如下，且一直F(0) = 0

Input:

6

1 3 4

Output:

2

?

import java.util.Scanner;public class Main {static int[] c = new int[10];static int[] f = new int[10];static int sum;static Scanner in = new Scanner(System.in);public static void main(String[] args) {sum = in.nextInt();int n = in.nextInt();c[1] = 1;for (int i = 2; i <= n; i++) {c[i] = in.nextInt();}System.out.println(changeMaking(n));}private static int changeMaking(int n) {for (int i = 1; i <= sum; i++) {int temp = 99999999;int j = 1;while (j <= n && i >= c[j]) {temp = Math.min(f[i-c[j]], temp);j++;}f[i] = temp +1;}return f[sum];} }

3、硬幣收集問題：在n*m格模板中放有一些硬幣，每格的硬幣數目最多為一個。從左上方開始收集，盡可能收集多的硬幣直到右下角對于每個單元格來說，只能取對應右邊一格或者下邊一格的硬幣。試求出最大的硬幣數及相應的路徑。思路：我們假設F(i, j)為行走到(i, j)所能收集到的最大硬幣數。單元格(i, j)可以經由上方(i-1, j)和左側單元格(i, j-1)到達。單元格(i-1 ,j)對應的最大硬幣數為F(i-1, j)，(i, j-1)對應的最大硬幣數為F(i, j - 1)。當然，第一行單元格上方沒有單元格，第一列單元格左邊沒有單元格，即F(i-1, j) = 0，F(i, j-1) = 0，所以其遞推公式為：

?

Input:

5 6

0 0 0 0 1 0

0 1 0 1 0 0

0 0 0 1 0 1

0 0 1 0 0 1

1 0 0 0 1 0

Output:

5

?

import java.util.Scanner;public class Main {static int[][] c = new int[10][10];static int[][] f = new int[10][10];static int sum, n, m;static Scanner in = new Scanner(System.in);public static void main(String[] args) {n = in.nextInt();m = in.nextInt();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {c[i][j] = in.nextInt();}}f[1][1] = c[1][1];System.out.println(coinCollection());}private static int coinCollection() {/*** 左上角，初始位置* */f[1][1] = c[1][1];/*** 第一列只有上方來的* */for (int i = 2; i <= n; i++) {f[i][1] += f[i-1][1];}/*** 第一行只有左側來的* */for (int j = 2; j <= m; j++) {f[1][j] += f[1][j-1];}for (int i = 2; i <= n; i++) {for (int j = 2; j <= m; j++) {f[i][j] = Math.max(f[i-1][j], f[i][j-1]) + c[i][j];}}return f[n][m];} }

?

?

?

?

?

?

?

總結

以上是生活随笔為你收集整理的动态规划在求解硬币问题中的应用（JAVA）--币制最大化、找零问题、硬币收集问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。