品牌营销型网站建设,男科医院网站建设策略,千锋教育成都校区,wordpress文章图片左右滑动目录
一、动态规划简介
二、利用动态规划解决问题
1、斐波拉契序列
2、拆分词句
3、三角形最小路径和
4、不同的路径数目#xff08;一#xff09;
5、带权值的最小路径和
6、求路径ii
7、01背包
8、不同子序列
9、编辑距离
10、分割回文串 一、动态规划…目录
一、动态规划简介
二、利用动态规划解决问题
1、斐波拉契序列
2、拆分词句
3、三角形最小路径和
4、不同的路径数目一
5、带权值的最小路径和
6、求路径ii
7、01背包
8、不同子序列
9、编辑距离
10、分割回文串 一、动态规划简介 动态规划就是分治思想的延伸通俗来讲就是大事化小小事化了。 在将大问题划分为小问题的分治过程中将小问题的处理结果进行保存以便后面处理大问题时使用到这些结果。 动态规划具有三个特点 将原来的问题分解成几个相似的子问题。所有的子问题只需要解决一次。存储子问题的解。动态规划的本质状态的定义和状态方程的定义。 动态规划问题的四个要素 状态的定义。状态间的转移方程的定义。状态的初始化。返回结果。定义的状态之间要形成递推关系。 动态规划问题的使用场景求最值、可不可行、是不是、求方案的个数。 二、利用动态规划解决问题
1、斐波拉契序列 题目链接斐波拉契数列 大家都知道斐波那契数列现在要求输入一个正整数 n 请你输出斐波那契数列的第 n 项。 题目分析 状态的定义F(i) 表示斐波拉契数列的第i项。状态间的转移方程F(i) F(i-1)F(i-2)。初始化F(1) 1,F(2) 1。返回值F(n)。代码实现
public int Fibonacci(int n) {int[] fib new int[n1];fib[1] 1;fib[2] 1;for(int i 3;i n;i){fib[i] fib[i-1] fib[i-2];}return fib[n];} 2、拆分词句 题目链接拆分词句 给定一个字符串s和一组单词dict判断s是否可以用空格分割成一个单词序列使得单词序列中所有的单词都是dict中的单词序列可以包含一个或多个单词。 例如: 给定s“nowcode” dict[now, code]. 返回true因为nowcode可以被分割成now code. 题目分析 要判断分割的单词序列是否都是dict中的单词因为分割是从前往后进行分割那么我们就可以给每个字符设置出一个状态true表示可以分割如果子状态canSplit[j]为true也就是前面一部分在dict中那么判断后面j~i是否为dict中的元素如果是就将canSplit[i]置为true继续向后判断由于要判断这个s分割的单词都在dict中所以就创建canSplit数组时需要增加一个元素canSplit[s.length()]来表示还有一个特殊情况如果仅仅分割s的第一个字符为dict中的元素那么其子问题的状态怎么设定所以就将canSplit[0]true表示0下标之前的状态为true综上利用动态规划可以分析出 状态的定义 canSplit[i]:表示该字符对应的下标是否可以拆分状态间转移方程的定义jicanSplit[i]truedict.contains(subString(j,i))状态初始化canSplit[0]true返回结果canSplit[字符串长度]的状态表示整个字符串分割的单词是都在dict中。代码实现
public boolean wordBreak(String s, SetString dict) {if(s null || dict null){return false;}boolean[] canSplit new boolean[s.length()1];canSplit[0] true;for(int i 1;i s.length();i){for(int j 0;j i;j){if(canSplit[j]dict.contains(s.substring(j,i))){canSplit[i] true;}}}return canSplit[s.length()];}
3、三角形最小路径和 题目链接三角形最小路径和 给定一个正三角形数组自顶到底分别有 12345...n 个元素找出自顶向下的最小路径和。每一步只能移动到下一行的相邻节点上相邻节点指下行种下标与之相同或下标加一的两个节点。 例如当输入[[2],[3,4],[6,5,7],[4,1,8,3]]时对应的输出为11 所选的路径如下图所示 题目分析 要求从三角形的顶点到底部的最小路径那么就需要求出其上层的最小路径假设F(i,j)表示到结点的最小路径如果该结点是最短路径上的点就直接将该点的值修改为顶点到该点的最小路径和就不用再开辟新的空间了又由于每一步只能移动到下一行的相邻节点上所以结点(i,j)的最短路径F(i,j)min(F(i-1,j)F(i-1,j-1)),但是对于三角形两个边上的点其上层的最小路径只需加上其上层的一个点:如果j0F(i,j)F(i-1,j);如果ijF(i,j)F(i-1,j)于是就利用动态规划分析得出 状态的定义F(i,j):到结点(i,j)的最小路径和(包含结点(i,j)的值)状态间转移方程的定义F(i,j)min(F(i-1,j)F(i-1,j-1))如果j0F(i,j)F(i-1,j);如果ijF(i,j)F(i-1,j)状态初始化F(0,0)val((0,0)结点的值)返回值min(F(底部结点))代码实现
public int minTrace (int[][] triangle) {if(triangle null){return 0;}int row triangle.length;for(int i 1;i row;i){for(int j 0;j i;j){if(j 0){triangle[i][j] triangle[i-1][j];}else if( j i){triangle[i][j] triangle[i-1][j-1];}else{triangle[i][j] Math.min(triangle[i-1][j-1],triangle[i-1][j]);}}}int mintriangle[row-1][0];for(int i 1;i triangle[row - 1].length;i){if(triangle[row - 1][i] min){min triangle[row -1][i];}}return min;} 上述思路是从顶点到点(i,j)的最短路径那么也可以从点(i.j)到顶点的最短路径就从倒数第二层开始遍历那么利用动态规划分析可得 状态的定义F(i,j) 为底部到点i,j的最短路径。状态间转移方程的定义F(i,j)min(F(i1,j)F(i1,j1))。状态初始化F(i,j)triangle(i,j)。返回值F(0,0)。代码实现
public int minTrace (int[][] triangle) {if(triangle null){return 0;}int rows triangle.length;for(int i rows - 2;i 0;i--){for(int j 0; j i;j){triangle[i][j] Math.min(triangle[i1][j1],triangle[i1][j]);}}return triangle[0][0];}
4、不同的路径数目一 题目链接不同的路径数目一 一个机器人在m×n大小的地图的左上角起点。 机器人每次可以向下或向右移动。机器人要到达地图的右下角终点。 可以有多少种不同的路径从起点走到终点 备注m和n小于等于100,并保证计算结果在int范围内 题目分析 由于机器人每次可以向下或向右移动对于到达第一行和第一列的点只有一种路径经过分析到达其他点的路径方案为左边点的路径方案数和上边点的路径方案数之和。所以利用动态规划分析如下 状态的定义F(i,j)表示起点到点ij的路径方案数。状态间的转移方程F(i,j) F(i-1,j) F(i,j-1)。状态初始化F(i,1)1,F(i,j)1,到达第一行和第一列的点只有一种路径。返回值F(m,n)。代码实现
public int uniquePaths (int m, int n) {int[][] path new int[m1][n1];for(int i 1; i n;i){path[1][i] 1;}for(int i 1; i m;i){path[i][1] 1;}for(int i 2; i m;i){for(int j 2;j n;j){path[i][j] path[i][j-1] path[i-1][j];}}return path[m][n];}
5、带权值的最小路径和 题目链接带权值的最小路径和 给定一个由非负整数填充的m x n的二维数组现在要从二维数组的左上角走到右下角请找出路径上的所有数字之和最小的路径。 注意你每次只能向下或向右移动。 题目分析 利用动态规划分析如下 状态的定义F(i,j)表示起点到坐标为(i,j)的最小路径和。状态间的转移方程F(i,j) min(F(i-1,j), F(i,j-1))。状态初始化F(i,0) F(i-1,0);F(0,j) F(0,j-1)第一行和第一列元素进行初始化。返回值F(m-1,n-1)。代码实现
public int minPathSum (int[][] grid) {int rows grid.length;int cols grid[0].length;for(int i 1; i rows;i){grid[i][0] grid[i-1][0];}for(int i 1; i cols;i){grid[0][i] grid[0][i-1];}for(int i 1; i rows;i){for(int j 1;j cols;j){grid[i][j] Math.min(grid[i-1][j],grid[i][j-1]);}}return grid[rows-1][cols-1];}
6、求路径ii 题目链接求路径ii 给定一个m*n的地图其中加入了一些障碍。每次只能向下或者向右走问从左上角走到右下角有多少不同的路径 分别用0和1代表空区域和障碍 例如 下图表示有一个障碍在3*3的图中央。 [[0,0,0],[0,1,0],[0,0,0]
] 有2条不同的路径 备注m和n不超过100. 题目分析 由动态规划思想分析可得 状态的定义F(i,j)表示起点到点ij的路径方案数。状态间的转移方程如果obstacleGrid(i,j)1,F(i,j)0,否则F(i,j)F(i-1,j)j0F(i,j)F(ij-1)i0F(i,j) F(i-1,j) F(i,j-1)(i!0,j!0)。状态初始化F(0,0)obstacleGrid(0,0)10:1。返回值F(m-1,n-1)。代码实现
public static int uniquePathsWithObstacles (int[][] obstacleGrid) {if(obstacleGridnull)return 0;int i,j;int mobstacleGrid.length;int nobstacleGrid[0].length;int[][]fnew int[m][n];if(obstacleGrid[0][0]1){return 0;}else{f[0][0]1;}for(i0;im;i){for(j0;jn;j){if(obstacleGrid[i][j]1){f[i][j]0;continue;}if(i0j!0){f[i][j]f[i][j-1];}if(i!0j0){f[i][j]f[i-1][j];}if(i!0j!0){f[i][j]f[i-1][j]f[i][j-1];}}}return f[m-1][n-1];}
7、01背包 题目链接01背包 已知一个背包最多能容纳体积之和为v的物品现有 n 个物品第 i 个物品的体积为 vi , 重量为 wi求当前背包最多能装多大重量的物品? 题目分析 状态的定义F(i,j)表示i个物品和体积为j的重量。状态间的转换方程 如果空间不足F(i,j) F(i-1,j).如果空间充足就要判断是否放入元素取max( F(i-1,j),(F(i-1,j-vi)wi))。初始化第0行和第0列的元素为0表示未放任何物品和体积为0的情况。返回值F(m,n)。代码实现 /*** 计算01背包问题的结果* param V int整型 背包的体积* param n int整型 物品的个数* param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i1个物品的vi,wi* return int整型*/
public static int knapsack (int V, int n, int[][] vw) {int[][] maxValue new int[n1][V1];for(int i 1; i n;i){for(int j 1; j V;j){if(j vw[i-1][0]){maxValue[i][j] maxValue[i-1][j];}else{maxValue[i][j] Math.max(maxValue[i-1][j],maxValue[i-1][j-vw[i-1][0]]vw[i-1][1]);}}}return maxValue[n][V];
}
8、不同子序列 题目链接不同的子序列 给定两个字符串S和T返回S子序列等于T的不同子序列个数有多少个 字符串的子序列是由原来的字符串删除一些字符也可以不删除在不改变相对位置的情况下的剩余字符例如ACEis a subsequence ofABCDE但是AEC不是 例如 Snowcccoder, T nowccoder 返回3 题目分析 状态的定义dp[i][j]表示以i-1结尾的字符串S等于以j-1结尾的字符串T子序列的个数。状态间的转移方程dp[i][j](S[i-1]T[j-1])?(dp[i-1][j-1]dp[i-1][j]):dp[i-1][j].初始化dp[0][j] 0,表示S字符串为空dp[i][0] 1表示T字符串为空dp[0][0]1表示S和T都为空。返回值dp[S.length()][T.length()]。代码实现 public int numDistinct (String S, String T) {int lenS S.length();int lenT T.length();int[][] dp new int[lenS1][lenT1];for(int i 0;i lenS;i){dp[i][0] 1;}for(int i 1;i lenS;i){for(int j 1;j lenT;j){if(S.charAt(i-1) T.charAt(j-1)){dp[i][j] dp[i-1][j-1] dp[i-1][j];}else{dp[i][j] dp[i-1][j];}}}return dp[lenS][lenT];}
9、编辑距离 题目链接编辑距离 给定两个单词word1和word2请计算将word1转换为word2至少需要多少步操作。 你可以对一个单词执行以下3种操作 a在单词中插入一个字符 b删除单词中的一个字符 c替换单词中的一个字符 题目分析 状态的定义dp[i][j]表示前i-1的word1转换为前j-1的word2需要多少步操作。状态间的转换方程dp[i][j](word1[i-1]word2[j-1])?dp[i-1][j-1]:(min(dp[i-1][j]1, dp[i][j-1]1dp[i-1][j-1]1)dp[i-1][j]1表示删除word1的第i-1个字符dp[i][j-1]1表示新增word1的第i-1个字符dp[i-1][j-1]1表示替换word1的第i-1个字符。初始化dp[0][0] 0,dp[0][j] j,dp[i][0] i。返回值p[word1.length()][word2.length()]。代码实现
public int minDistance (String word1, String word2) {int len1 word1.length();int len2 word2.length();int[][] dp new int[len11][len21];for(int i 1;i len1;i){dp[i][0] i;}for(int j 1;j len2;j){dp[0][j] j;}for(int i 1;i len1;i){for(int j 1;j len2;j){if(word1.charAt(i-1) word2.charAt(j-1)){dp[i][j] dp[i-1][j-1];}else{int min1 Math.min(dp[i-1][j-1],dp[i-1][j]);int min2 Math.min(dp[i][j-1],dp[i-1][j]);dp[i][j] Math.min(min1,min2) 1;}}}return dp[len1][len2];}
10、分割回文串 题目链接分割回文串 给出一个字符串s分割s使得分割出的每一个子串都是回文串 计算将字符串s分割成回文分割结果的最小切割数 例如:给定字符串saab, 返回1因为回文分割结果[aa,b]是切割一次生成的。 题目分析 状态的定义dp[i]表示到第i个字符分割的次数。状态间的转移方程dp[i] min(dp[i],dp[j]1)。初始化dp[i]表示到第i个字符的最大分割次数。返回值dp[s.length()]。public boolean isPalindrome(String s){int begin 0;int end s.length()-1;while(begin end){if(s.charAt(begin) s.charAt(end)){begin;end--;}else{return false;}}return true;}public int minCut (String s) {int len s.length();int[] dp new int[len1];for(int i 0;i len;i){dp[i] i-1;}for(int i 1;i len;i){for(int j 0;ji;j){if(isPalindrome(s.substring(j,i))){dp[i] Math.min(dp[i],dp[j]1);}}}return dp[len];}
