算法学习 | 动态规划经典练习题合集_动态规划习题

目录

带权值的最小路径和

背包问题（二）

分割回文串-ii

编辑距离 

---

带权值的最小路径和

OJ链接：CC86-带权值的最小路径和

题目描述 

给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。
注意：你每次只能向下或向右移动。

例如

输入：[[1,2],[5,6],[1,1]]

输出：8

根据题目要求，每次只能向下或向右移动

对题目进行dp状态分析 

状态定义：F(i，j)：从(0，0)到(i，j)的最短路径和

状态方程：F(i，j) = min( F(i-1，j)，F(i，j-1) ) + grid[i][j]

初始值：F(0，0) = grid[0][0]

返回值：F(m - 1，n - 1)

 

import java.util.*;
public class Solution {
     状态定义：F(i，j)：从(0，0)到(i，j)的最短路径和
     状态方程：F(i，j) = min(F(i - 1，j)，F(i，j - 1)) + grid[i][j]
     初始值：F(0，i) = 1，F(i，0) = 1;
     返回值：F(m-1，n-1)
      */
    public int minPathSum (int[][] grid) {
        // write code here
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];               
            }
        }
        return dp[m-1][n-1];
    }
}

背包问题（二）

OJ链接：背包问题（二） 

题目描述 

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

例如

输入：m = 10   A = [2, 3, 5, 7]   V = [1, 5, 2, 4] 

返回：9

dp状态分析

状态定义：F(i，j)：表示前i个物品放在大小为j的背包中所获得的最大价值

状态递推：有两种情况：一种是可以放下，一种是放不下

   ①如果可以放下：F(i，j) = max{ F(i - 1，j)，F(i - 1，j - a[i]) + v[i] }

   ②如果放不下：F(i，j) = F(i - 1，j)，因为背包的大小不足以放下第i个物品，因此这个状态的值应该为上一个状态的值

初始值：第0行和第0列的值都为0，表示未装物品

返回值：F(n，m)

public class Solution {
     状态定义：F(i，j)：前i个物品放在大小为j的背包中所获得的最大价值
     状态递推：如果放不下：F(i，j) = F(i-1，j)
              如果能放下：F(i，j) = max{F(i-1, j), F(i-1, j-a[i]) + v[i]}
     初始值：F(0, j) = F(i, 0) = 0
     返回值：F(n, m)，m为背包大小，n为物品数量
     */
    public int backPackII(int m, int[] a, int[] v) {
        // write your code here
        int n = a.length;
        int[][] dp = new int[n + 1][m + 1];
        //初始化
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j < a[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    int newValue = dp[i - 1][j - a[i - 1]] + v[i - 1];
                    dp[i][j] = Math.max(newValue, dp[i - 1][j]);
                }
            }
        }
        return dp[n][m];
    }
}

分割回文串-ii

OJ链接：CC19-分割回文串-ii

题目描述

给出一个字符串s，分割s使得分割出的每一个子串都是回文串

计算将字符串s分割成回文分割结果的最小切割数

例如:给定字符串s="aab",

返回1，因为回文分割结果["aa","b"]是切割一次生成的。

dp状态分析

状态定义：F(i)：到第i个字符最小的拆分次数

状态递推：F(i) = min(F(i), F(j) + 1)
初始化：F(i) = i - 1（表示到第i个字符所需要的最大拆分次数）

返回值：F(n)

import java.util.*;
public class Solution {
     /**
     状态定义：F(i)：到第i个字符最小的拆分次数
     状态递推：F(i) = min(F(i), F(j) + 1)
     初始值：F(i) = i - 1（表示到第i个字符所需要的最大拆分次数）
     返回值：F(n)
      */
    public int minCut (String s) {
        // write code here
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = i - 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (isPal(s, j, i - 1)) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }
    private boolean isPal(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

编辑距离 

OJ链接：CC77-编辑距离

题目描述

给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。
你可以对一个单词执行以下3种操作：
a）在单词中插入一个字符
b）删除单词中的一个字符
c）替换单词中的一个字符 

例如

输入：“ab”，“bc”

输出：2 

dp状态分析

状态定义：F(i，j)：word1前i个字符转换为word2的前j个字符需要的最少步数

状态方程：F(i，j) = min{ F(i-1，j)+1，F(i，j-1)+1，F(i-1，j-1)+(word1[i] == word2[j] ? 0 : 1) }

初始化：F(i，j) = min{F(i-1, j)+1, F(i, j-1)+1, F(i-1, j-1)+(word1[i] == word2[j] ? 0 : 1)}

初始值一定要是空字符串

F(i，0) = i：word与空串的编辑距离，删除操作

F(0，i) = i：空串与word的编辑距离，增加操作

返回值：F(m，n)

 

import java.util.*;
public class Solution {
     /**
     状态定义：F(i，j)：word1的前i个字符变成word2的前j个字符的最小步数
     状态方程：F(i，j) = min{F(i-1, j)+1, F(i, j-1)+1, F(i-1, j-1)+(word1[i] == word2[j] ? 0 : 1)}
     初始化：
          F(i，0) = i：word与空串的编辑距离，删除操作
          F(0，i) = i：空串与word的编辑距离，增加操作
     返回值：F(m，n)
      */
    public int minDistance (String word1, String word2) {
        // write code here
        //word与空串之间的编辑距离为word长度
        if (word1.isEmpty() || word2.isEmpty()) {
            return Math.max(word1.length(), word2.length());
        }
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
                //判断word1的第i个字符与word2的第j个字符是否相等
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    //字符相等，F(i-1, j-1)编辑距离不变
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                } else {
                    //字符不相等，F(i-1, j-1)编辑距离+1
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[m][n];
    }
}