当前位置：网站首页>Summary of leetcode's dynamic programming 5
Summary of leetcode's dynamic programming 5
2022-07-01 14:09:00 【nuist__ NJUPT】
leetcode Summary of dynamic programming 5
1- The smallest of two strings ASCII Delete and
Topic link ： The title link is here ！！！
Ideas ： Dynamic programming
dp[i][j] Said to i-1 a null-terminated string s1 And with j-1 a null-terminated string s2 Keep the same deleted minimum ASCII character .
initialization dp Array
If one of them is an empty string , In order to keep them the same , You need to delete all the characters of another .
If s1.charAt(i-1)==s2.charAt(j-1), You don't need to delete , The recurrence formula is as follows ：
dp[i][j] = dp[i-1][j-1]
otherwise , You need to delete one of the two ASCII Small , Recursive down ：
dp[i][j] = Math.min(dp[i-1][j]+(s1.charAt(i-1)), dp[i][j-1]+(s2.charAt(j-1))) ;
AC The code is as follows ：
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int [][] dp = new int [s1.length()+1][s2.length()+1] ;
for(int i=1; i<=s1.length(); i++){
dp[i][0] = dp[i-1][0] + s1.charAt(i-1) ;
}
for(int j=1; j<=s2.length(); j++){
dp[0][j] = dp[0][j-1] + s2.charAt(j-1) ;
}
for(int i=1; i<=s1.length(); i++){
for(int j=1; j<=s2.length(); j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] ;
}else{
dp[i][j] = Math.min(dp[i-1][j]+(s1.charAt(i-1)), dp[i][j-1]+(s2.charAt(j-1))) ;
}
}
}
return dp[s1.length()][s2.length()] ;
}
}
2- Delete and get points
Topic link ： The title link is here ！！！
Ideas ： take nums The array becomes the sum of each number , Then it becomes the problem of house raiding , You can only choose between stealing and not stealing every time .
class Solution {
public int deleteAndEarn(int[] nums) {
int [] value = new int [10001] ;
int [] dp = new int [value.length] ;
for(int i=0; i<nums.length; i++){
value[nums[i]] += nums[i] ;
}
dp[0] = value[0] ;
dp[1] = Math.max(value[0],value[1]) ;
for(int i=2; i<value.length; i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+value[i]) ;
}
return dp[dp.length-1] ;
}
}
3- Rotate the numbers
Topic link ： The title link is here ！！！
Ideas 1： Judge whether it is a good number , If yes , Then add 1
Satisfying the following two is a good number ：
1- It doesn't contain 3,4,7 One of them
2- contain 2,5,6,9 One of them
class Solution {
public int rotatedDigits(int n) {
int cnt = 0 ;
for(int i=1; i<=n; i++){
if(goodNumder(i)){
cnt ++ ;
}
}
return cnt ;
}
public boolean goodNumder(int n){
String str = String.valueOf(n) ;
boolean flag = false ;
for(int i=0; i<str.length(); i++){
if(str.charAt(i)=='3' || str.charAt(i)=='4' || str.charAt(i)=='7'){
return false ;
}else if(str.charAt(i)=='2' || str.charAt(i)=='5' || str.charAt(i)=='6' || str.charAt(i)=='9'){
flag = true ;
}
}
return flag ;
}
}
4- The longest Fibonacci subsequence length
Topic link ： The title link is here ！！！
Ideas ：dp[i][j] From i To j The longest Fibonacci sequence of positions , use map Store the corresponding elements and subscripts , If each group (3 A digital ) The first number of Fibonacci appears , Update dp Array .
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length ;
if(n<3){
return 0 ;
}
Map<Integer,Integer> map = new HashMap<>() ;
for(int i=0; i<n; i++){
map.put(arr[i],i) ;
}
int [][] dp = new int [n][n] ;
int res = 0 ;
for(int i=0; i<n;i++){
for(int j=0; j<i; j++){
if(map.containsKey(arr[i]-arr[j]) && arr[i]-arr[j]<arr[j]){
int k = map.get(arr[i]-arr[j]) ;
dp[j][i] = Math.max(dp[k][j]+1,dp[j][i]) ;
dp[j][i] = Math.max(dp[j][i],3) ;
}
res = Math.max(res, dp[j][i]) ;
}
}
return res ;
}
}
5- The best time to buy and sell stocks includes handling fees
Topic link ： The title link is here ！！！
Ideas ： The first i There are two states in heaven , Holding or not holding shares
If holding shares , Then it can be divided into two situations ：1- Held the day before ,2- Buy today
If you do not hold shares , There are also two situations ：1- Didn't hold... The day before ,2- Sell today
We finally found that we didn't hold it in turn , That's our answer
dp[i][1]: It means the first one i Day holding
dp[i][0]: It means the first one i Days don't hold
class Solution {
public int maxProfit(int[] prices, int fee) {
int [][] dp = new int [prices.length][2] ;
dp[0][0] = 0;
dp[0][1] = -prices[0] ;
for(int i=1;i<prices.length; i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee) ;
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]) ;
}
return dp[dp.length-1][0] ;
}
}
6- The descent path is the smallest and
Topic link ： The title link is here ！！！
Ideas ： Bottom up , Put the smallest of the three below each time , Add to top , Finally, the smallest in the first line is the minimum sum of the descent path .
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length ;
for(int row=n-2; row>=0; row--){
for(int col=0; col<n; col++){
int value = matrix[row+1][col] ;
if(col-1>=0){
value = Math.min(matrix[row+1][col-1],value) ;
}
if(col+1<n){
value = Math.min(matrix[row+1][col+1],value) ;
}
matrix[row][col] += value ;
}
}
int ans = Integer.MAX_VALUE ;
for(int res : matrix[0]){
ans = Math.min(ans, res) ;
}
return ans ;
}
}
7- Number of combinations IV
Topic link ： The title link is here ！！！
Ideas ：dp[x]: The sum of the selected elements is equal to x Number of alternatives .
class Solution {
public int combinationSum4(int[] nums, int target) {
int [] dp = new int [target+1] ;
dp[0] = 1 ;
for(int i=0; i<=target; i++){
for(int num : nums){
if(i-num>=0){
dp[i] += dp[i-num] ;
}
}
}
return dp[target] ;
}
}
8- The best time to buy and sell stocks IV
Topic link ： The title link is here ！！！
Ideas ： Dynamic programming
We use it buy[i][j] For an array prices[0…i] In terms of price , Proceed exactly j transaction , And currently holds a stock , The maximum profit in this case ; use sale[i][j] It means that j transaction , And does not currently hold shares , The maximum profit in this case .
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length ;
if(n==0){
return 0;
}
int [][] buy = new int [n][k+1] ;
int [][] sale = new int [n][k+1] ;
buy[0][0] = -prices[0] ;
for (int i = 1; i <= k; ++i) {
buy[0][i] = sale[0][i] = Integer.MIN_VALUE / 2;
}
for(int i=1; i<n; i++){
buy[i][0] = Math.max(buy[i-1][0],sale[i-1][0]-prices[i]) ;
for(int j=1; j<=k; j++){
buy[i][j] = Math.max(buy[i-1][j],sale[i-1][j]-prices[i]) ;
sale[i][j] = Math.max(sale[i-1][j],buy[i-1][j-1]+prices[i]) ;
}
}
int max = Integer.MIN_VALUE ;
for(int sell : sale[n-1]){
max = Math.max(sell,max) ;
}
return max ;
}
}
9-01 matrix
Topic link ： The title link is here ！！！
Ideas ： Recursion from the upper left corner and the lower right corner .
The recursive expression is as follows ：
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length ;
int n = mat[0].length ;
int [][] dp = new int [m][n] ;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
dp[i][j] = (mat[i][j] == 0 ? 0 : Integer.MAX_VALUE/2);
}
}
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i-1>=0){
dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1) ;
}
if(j-1>=0){
dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1) ;
}
}
}
for(int i=m-1; i>=0; i--){
for(int j=n-1; j>=0; j--){
if(i+1<m){
dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1) ;
}
if(j+1<n){
dp[i][j] = Math.min(dp[i][j], dp[i][j+1]+1) ;
}
}
}
return dp ;
}
}
10- Divisor game
Topic link ： The title link is here ！！！
Ideas ： We define dp[i] Represents the current number i Whether the first hand is in the state of winning or losing ,}true The first to win ,alse It means that the first hand will lose , Recursion after going , If the state after taking a number is inevitable , Then the current state must be winning .
class Solution {
public boolean divisorGame(int n) {
if(n==1){
return false ;
}
if(n==2){
return true ;
}
boolean [] dp = new boolean[n+1] ;
dp[1]=false ;
dp[2]=true ;
for(int i=3; i<=n; i++){
for(int j=1; j<i; j++){
if((i%j)==0 && !dp[i-j]){
dp[i] = true ;
break ;
}
}
}
return dp[n] ;
}
}
No silicon step , A thousand miles , Don't product the little stream , Nothing can be a river .
边栏推荐
- MySQL日志
- Machine learning summary (I): linear regression, ridge regression, Lasso regression
- 8款最佳实践，保护你的 IaC 安全！
- “国防七子”经费暴增，清华足足362亿元，甩第二名101亿 ｜全国高校2022预算大公开...
- "National defense seven sons" funding soared, with Tsinghua reaching 36.2 billion yuan, ranking second with 10.1 billion yuan. The 2022 budget of national colleges and universities was made public
- 百度上找的期货公司安全吗?期货公司怎么确定正规
- Station B was scolded on the hot search..
- 佩服，阿里女程序卧底 500 多个黑产群……
- GET请求如何传递数组参数
- 清华章毓晋老师新书：2D视觉系统和图像技术（文末送5本）
猜你喜欢
【241. 为运算表达式设计优先级】
【修复版】仿我爱看电影网站模板/海洋CMS影视系统模板
Build your own website (21)
2022 PMP project management examination agile knowledge points (6)
2022上半年英特尔有哪些“硬核创新”？看这张图就知道了！
Use lambda function URL + cloudfront to realize S3 image back to source
【Flask】Flask启程与实现一个基于Flask的最小应用程序
Fiori applications are shared through the enhancement of adaptation project
Etcd 概要 机制 和使用场景
Phpcms realizes the direct Alipay payment function of orders
随机推荐
A new book by teacher Zhang Yujin of Tsinghua University: 2D vision system and image technology (five copies will be sent at the end of the article)
Applet - applet chart Library (F2 chart Library)
[anwangbei 2021] Rev WP
QT学习管理系统
小程序-小程序图表库（F2图表库）
力扣解法汇总241-为运算表达式设计优先级
How to pass array parameters in get request
建立自己的网站（21）
当主程架构游戏的时候，防止到处调用减少耦合性，怎么开放接口给其他人调用呢？
【修复版】仿我爱看电影网站模板/海洋CMS影视系统模板
C language course design topic
Sign APK with command line
被裁三個月，面試到處碰壁，心態已經開始崩了
Admire, Ali female program undercover more than 500 black production groups
Leetcode question 1: sum of two numbers (3 languages)
【NLP】预训练模型——GPT1
Use of Oracle database objects
【剑指 Offer】55 - II. 平衡二叉树
Phpcms realizes the direct Alipay payment function of orders
Realize queue with stack and stack with queue (C language \leetcode\u 232+225)