当前位置:网站首页>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 .
边栏推荐
- El form item regular verification
- 光环效应——谁说头上有光的就算英雄
- 学会使用LiveData和ViewModel,我相信会让你在写业务时变得轻松
- Scheme of printing statistical information in log
- Liu Dui (fire line safety) - risk discovery in cloudy environment
- "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
- 我们该如何保护自己的密码?
- Six years of technology iteration, challenges and exploration of Alibaba's globalization and compliance
- In depth cooperation | Taosi data cooperates with changhongjia Huawei customers in China to provide tdengine with powerful enterprise level products and perfect service guarantee
- Go整合Logrus实现日志打印
猜你喜欢
Enter the top six! Boyun's sales ranking in China's cloud management software market continues to rise
既不是研发顶尖高手,也不是销售大牛,为何偏偏获得 2 万 RMB 的首个涛思文化奖?
清华章毓晋老师新书:2D视觉系统和图像技术(文末送5本)
sqlilabs less-11~12
Phpcms realizes the direct Alipay payment function of orders
队列的基本操作(C语言实现)
被裁三個月,面試到處碰壁,心態已經開始崩了
Etcd 概要 机制 和使用场景
QT社团管理系统
开源实习经验分享:openEuler软件包加固测试
随机推荐
The integration of computing and Internet enables the transformation of the industry, and the mobile cloud lights up a new roadmap for the future of digital intelligence
[241. Design priority for operation expression]
[sword finger offer] 55 - I. depth of binary tree
sqlilabs less-11~12
Dragon lizard community open source coolbpf, BPF program development efficiency increased 100 times
WebSocket(简单体验版)
SWT / anr problem - how to open binder trace (bindertraces) when sending anr / SWT
用对场景,事半功倍!TDengine 的窗口查询功能及使用场景全介绍
[IOT design. Part I] stm32+ smart cloud aiot+ laboratory security monitoring system
Liu Dui (fire line safety) - risk discovery in cloudy environment
当你真的学会DataBinding后,你会发现“这玩意真香”!
6年技术迭代,阿里全球化出海&合规的挑战和探索
How to pass array parameters in get request
小程序- view中多个text换行
What class loading mechanisms does the JVM have?
SWT/ANR问题--当发送ANR/SWT时候如何打开binder trace(BinderTraces)
当主程架构游戏的时候,防止到处调用减少耦合性,怎么开放接口给其他人调用呢?
佩服,阿里女程序卧底 500 多个黑产群……
Why did you win the first Taosi culture award of 20000 RMB if you are neither a top R & D expert nor a sales Daniel?
SWT/ANR问题--如何捕获性能的trace