算法-动态规划DP小记

时间:2022-04-30 19:06:03

算法-动态规划DP小记

动态规划算法是一种比较灵活的算法,针对具体的问题要具体分析,其宗旨就是要找出要解决问题的状态,然后逆向转化为求解子问题,最终回到已知的初始态,然后再顺序累计各个子问题的解从而得到最终问题的解。

关键点就是找到状态转移方程和初始边界条件,说白了就是要找到“递推公式”和初始值,然后计算时保存每一步中间结果,最后累加判断得到结果。

0.求数组最值

求数组最值方法很多,这里使用动态规划的思想来尝试处理,以便更好地理解DP的思想。为了方便这里假设数组a[i]大小为n,要找n个数当中的最大值。

设dp[i]表示第0...i个数的最大值,dp[i-1]表示第0...i-1个数的最大值,所以求前i个数的最大值时,已经知道前i-1个是的最大值是dp[i-1],那么只需要比较dp[i-1]和第i个数谁大就知道了,即dp[i] = max(dp[-1], a[i])。

	public int max(int[] a){
int len = a.length;
int[] dp = new int[len];
dp[0] = a[0];
for(int i=1; i<len; i++){
dp[i] = (dp[i-1] > a[i]) ? dp[i-1] : a[i];
}
return dp[len-1];
}

1.求最大公共子序列长度

给定一个字符串,想要删掉某些字符使得最后剩下的字符构成一个回文串(左右对称的字符串,如abcba),问最少删掉多少个字符可获得一个最长回文串。

    /**
* 本题求回文串最大长度就转化为求两个字符串的最长公共子序列(不一定连续)
* 策略:字符串可以看做是字符序列,即字符数组。
* 比如有序列A=a0,a1,a2...an;有序列B=b0,b1,b2,b3...bm;设A序列和B序列的公共子序列为C=c0,c1,c2,c3...ck。
* 设L[][]为公共子序列C的长度,L[i][j]的i、j分别表示A、B序列的字符下标,L[i][j]含义是A序列a0、a1、a2...ai和B序列b0、b1、b2、
* ...bj的公共子序列的长度。
*
* 1)如果A序列的i字符和B序列的j字符相等,那么就有ck=ai=bj,公共子序列C的长度L[i][j]=L[i-1][j-1]+1。
* 2)如果A序列的i字符和B序列的j字符不相等,若ai != ck则C为a0...ai-1和b0...bj的最长子序列,若bj != ck则C为a0...ai和b0...bj-1的最长子序列,
* 所以此时公共子序列长度为L[i][j] = max(L[i][j-1], L[i-1][j])。
*/
public static int lcs(String s){
if (s == null ) {
return -1;
}
String rs = new StringBuilder(s).reverse().toString();
char[] chars1 = s.toCharArray();
char[] chars2 = rs.toCharArray();//获得反序的字符串
int n = chars1.length;
int[][] dp = new int[n+1][n+1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(chars1[i] == chars2[j]){
dp[i][j] = dp[i-1][j-1] + 1;
}else {
dp[i][j] = dp[i][j-1] > dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
}
}
}
return n - dp[n][n]; }

2.硬币凑钱问题

只有面值为1元、3元、5元的硬币,数量足够。现在要凑够n元,求需要的最少硬币枚数。


/**
*
* @param n 目标总钱数
* @param coins 硬币数组【1,3,5】
* @return 返回凑够n元需要的最少硬币数
*/ public static int getLeastCoinAmount(int n, int[] coins){
if (coins == null || n < 0) {
return -1;
}
if (n == 0){
return 0;
}
int[] dp = new int[n+1]; //dp[i]=j表示凑够i元最少需要j枚硬币。数组长度设为(n+1)保证可以访问dp[n]。
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
} int coinValue = 0;
for (int i = 1; i <= n; i++) {//问题规模从小到大,直到达到目标面值
for (int j = 0; j < coins.length; j++) {//遍历所有面值的硬币,j表示硬币面值的下标
coinValue = coins[j];
if (i - coinValue >= 0 && 1 + dp[i-coinValue] < dp[i]){ //当前方案的硬币数更少,则使用当前方案
dp[i] = 1 + dp[i-coins[j]];
}
} }
return dp[n];
}

3.最长非降子序列

一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度。


/**
*
* 定义d(i)表示前i个数中"以A[i]结尾"的最长非降子序列的长度。
* 对序列A1...Ai,找到的最长子序列长度d[i]分两种情况:
* (1)包含最后一个数Ai,即d[i]=max{d[j]+1}(1<=j<i且Aj<=Ai),满足条件的Aj可能会有多个,选最大的d[j],如果Aj都大于Ai则d[j]=0;
* (2)不含最后一个数,即d[i]=d[i-1]
*
* 综上:d[i] = max{d[i-1], max{d[j]+1}}
*/
public static int longestIncreasingSubsequence(int[] a){
if (a == null) {
return -1;
}
if (a.length < 1){
return 0;
}
int len = a.length;
int[] dp = new int[len];//dp[i]系统自动初始化为0
dp[0] = 1;
for (int i = 1; i < len; i++) {//迭代,求序列0...len-1的最长子序列长度
for (int j = 0; j < i; j++) {//寻找Ai之前的序列,看是否有不大于Ai的数字Aj
if (a[j] <= a[i] && dp[i] < dp[j] + 1){//假设最长子序列包含最后一个数
dp[i] = dp[j] + 1;
}
}
//寻找Ai之前的序列如果Ai都小于Aj,此时dp[i]并没有被修改仍为初始值0。所以包含最后一个数的最长子序列就只有最后一个数自身,长1
dp[i] = Math.max(1, dp[i]);
//至此,已经求出了包含最后一个数的最长子序列的长度,和不包含最后一个数的最长子序列长度比较,取最大值为当前的最大长度
dp[i] = Math.max(dp[i], dp[i-1]);
}
return dp[len-1]; }

4.经典01背包问题

01背包问题:一个承重(或体积)为W的背包,可选物品有n个,第i个物品分别重w[i]和价值v[i],每个物品只能拿或不拿,求背包可放物品的最大价值。


/**
*
* 策略:这里的关键制约因素是背包只能承重w,而且每放入一个物品其承重就会减少。
* 因此定义maxValue=V[i][j],数组表示目前可选物品有i个:0、1...i-1,背包承重(剩余的存放重量)为j的最大价值。
* 现在假设已经知道了(i-1)个物品且剩余承重为j的最大价值V[i-1][j],那么考虑准备放入第i个物品的情况:
* (1)如果第i个物品的重量大于背包的剩余承重w_i>j,显然放不下了,所以此时V[i][j]=V[i-1][j];
* (2)w_i<=j,显然可以放下第i个物品,物品可以放得下,但是一定要装进来吗?如果装进的物品价值较低且较重,无疑会影响后续物品的装入情况。
* 所以还要考虑要不要放进来的子问题,V[i][j]=max{vi+V[i-1][j-wi], V[i-1][j]}。
*
* @param W
* @param n
* @param w
* @param v
* @return
*/
public static int knapsack(int W, int n, int[] w, int[] v){
if ( W < 1 || n < 1 || w == null || v == null) {
return -1;
}
int[][] dp = new int[n+1][W+1]; //可选的物品最多可以有n个,所以行数设为n+1。最大承重是W,所以列设为W+1。
int index = 0;
for (int i = 1; i <= n; i++) { //物品数肯定是从1开始。dp[0][j]系统初始化为0.
index = i-1;
for (int j = 1; j <= W ; j++) {//能装进的重量肯定是从1开始。dp[i][0]系统初始化为0.
if (w[index] > j){
dp[i][j] = dp[i-1][j];
}else {
dp[i][j] = Math.max(dp[i - 1][j - w[index]] + v[index], dp[i - 1][j]);
}
} } //找出是哪些物品放入背包
boolean[] isTaken = new boolean[n];//标记是否放入背包里
for (int i = n; i > 0 ; i--) {
if (dp[i][W] != dp[i-1][W]){
isTaken[i-1] = true;//装入
W -= w[i-1];//装入之后背包的承重减少
System.out.println(i-1);
}
}
return dp[n][W];//返回n个物品承重为W时的最大价值
} }

推荐文章:

动态规划:从新手到专家

动态规划解决01背包问题(java实现)