前言:
动态规划是十分常用的算法思想,本文针对动态规划的性质、求解例举了几种针对动态规划解法的题目,来解析动态规划解法的思想。
介绍:
动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度,因此它比回溯法、暴力法等要快许多。
解决动态规划问题的关键是要找到状态转移方程。将问题分解成最小的子问题,找到由子问题到全局问题的解决方案。
性质:
一般可以采用动态规划求解的问题的一般要具有以下几个性质:
(1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
(2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
(3) 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)。
求解动态规划问题的基本步骤:
(1)分析最优解的性质,并刻画其结构特征。
(2)递归的定义最优解。
(3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
(4)根据计算最优值时得到的信息,构造问题的最优解
举例:
方格走法
有一个X*Y的网格,某人要在此网格上从左上角到右下角,只能走格点且只能向右或向下走。请设计一个算法,计算该人共有多少种走法。给定两个正整数int x,int y,请返回该人的走法数目。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
int[][] array = new int[x+1][y+1];
array[0][0]=0;
//生成边界条件
for (int i = 1; i < x+1; i++) {
array[i][0]=1;
}
for (int i = 1; i < y+1; i++) {
array[0][i]=1;
}
for (int i = 1; i < x+1; i++) {
for (int j = 1; j < y+1; j++) {
array[i][j]=array[i-1][j]+array[i][j-1];
}
}
System.out.println(array[x][y]);
}
分析:例如走到[3,2]这个格子的数目一定是从[3,1]或[2,2]走过来的,那么[3,2]的步数也就是[3,1]和[2,2]之和,所以缩到最小,也就确定了最开始的状态,然后根据这个规律就能计算出[x,y]的步数。
字符串最小变换次数
给定两个字符串,已知可以使用三种方式进行变换
- 插入一个字符
- 删除一个字符
- 更改一个字符
请设计一个算法,找到两个字符串之间的经历几次最小变换,可以字符串1转换成字符串2
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str1 = "#" + scanner.next();
String str2 = "#" + scanner.next();
int[][] dp = new int[str1.length()][str2.length()];
// 初始化
for (int i = 1; i < str1.length(); i++)
dp[i][0] = i;
for (int i = 1; i < str2.length(); i++)
dp[0][i] = i;
for (int i = 1; i < str1.length(); i++) {
for (int j = 1; j < str2.length(); j++) {
if (str1.charAt(i) == str2.charAt(j))
dp[i][j] = dp[i - 1][j - 1];
else {
dp[i][j] = Math.min(dp[i - 1][j - 1],
Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
System.out.println(dp[str1.length() - 1][str2.length() - 1]);
}
分析: 可以用dp[i][j]来表示str1在i位置之前和str2在j位置之前字符的最小变换次数,那么dp[i][j]的取值与当前位置字符的判断有关。
递推公式:str1[i] == str2[j]=> dp[i][j] = dp[i-1][j-1]
str1[i] != str2[j]=> dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
为了初始化方便,可以在str1和str2的首部添加一个哨兵字符
走台阶
每次你可以走 1 或 2 个台阶需要走完n个台阶,有多少走法?
public static int f(int n){
if (n==1){
return 1;
}else if (n==2){
return 2;
}
return f(n-1)+f(n-2);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(f(n));
}
分析:第3个台阶其实就是第1个台阶走2步和第2个台阶走1步而来的,所以递推公式就是f(n)=f(n-1)+f(n-2)
即可。
public int FindGreatestSumOfSubArray(int[] array) {
int max = array[0];
int res = array[0];
for (int i = 1; i < array.length; i++) {
max = Math.max(max + array[i], array[i]);
res = Math.max(res, max);
}
return res;
}
分析:其实就是这个状态方程 max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )
就是说当累计的max变为负数时,就抛弃。不然这个max哪怕是1,相对于后面单独的累加,其实也是贡献,也就应加上的。
背包问题:
5kg的袋子
物品:物品只有一个,且不能拆分。
钱:6 10 12
Kg:1 2 4
1kg | 2kg | 3kg | 4kg | 5kg | |
---|---|---|---|---|---|
加第一个物品 | 6 | 6 | 6 | 6 | 6 |
加第二个物品 | 6(取上面第一个) | 10 | 16 | 16 | 16 |
加第三个物品 | 6 | 10 | 16 | 16 | 18 |
核心思想:
分解子问题,通过局部最大值得到全局最大。
//动态规划
public static void main(String[] args) {
int value[] = {60,100,120}; //每个物品的钱
int weight[] = {10,20,40}; //每个物品的重量 和上面的一一对应
int w = 50; //袋子的容积
int n = 3; //物品的个数
int dp[][] = new int[n+1][w+1]; //表示分割,成一个 小的表格
for(int i = 1; i<=n ;i++) { //表示物品往里面加
for(int cw = 1; cw <= w; cw ++) { //袋子在每一个容积下所装的最大的钱
if(weight[i - 1] <= cw) { //表示这个物品可以装
dp[i][cw] = Math.max(
value[i-1]+dp[i-1][cw-weight[i-1]], //我装新加的物品
dp[i-1][cw] //我不装这个新加的这个物品
);
}else {
dp[i][cw] = dp[i-1][cw]; //新加的这个装不下 ,那么就取前一个物品装值
}
}
}
System.out.println("袋子能装的最大价值:" + dp[n][w]);
}
分析:我们把5kg袋子拆分成1kg 1kg这样的来计算,每个格子的意思就是当前袋子在这个容量下能装的最大价值。行表示每次加的物品。
第二个进来时,如果此时袋子为2kg,我们知道在第一个物品进来时,2kg最多能装6块钱。,这时候如果我们选择装第二物品那么袋子里面的钱为10块,然后剩余0kg,那么物品1就不能装了。然后发现10块大于袋子里面原来的6快,所以我们选择装第二个 丢掉第一个。
第三个物品进来,如果此时袋子为5kg,我们如果选择加第三个物品,那么袋子容积还剩1kg,能得12块,我们找到上一列1kg袋子的最大价值,为6,所以总的为18.