自学内容网 自学内容网

动规当前总结

目标:最优化

方法:使用dp table消除重复子问题的重复计算

一个dp table, 一个dp函数

table的大小:目前感觉如果是地图都是原大小/长度,如果是字符串,target sum, 天数,可能会需要加一个位置

字符串:

最长回文子串

最短编辑距离

        dp数组意义:元素A字符串(截止到第i个字符)到B字符串(截止到第j个字符串)的最短编辑距离

        base case: 左边第一列【0】,第一行【0】,全部用i替代(全删除)

        状态转移 (min 删除/替换/增加)

word break: 用字典的词组成字符串

        dp数组意义:截止到第i个字符串的子串能否被拼出来

                                -1 代表未访问 0 代表不能 1 代表能

        base case:全-1

        先递归到最后,在递归出栈/后序位置设置dp数组的值

最长公共子串长度

        dp数组意义:

        【i】:字符串A截止到位置i的子串

        【j】字符串B截止到位置j的子串

        base case: 子串们最大的公共子串长度

数组相关:

最大乘积子序列

        审题考虑到元素正负,维护两个数组(截止到第i个元素最大/小)

最长递增非连续序列

        dp数组意义,截止到第i位严格递增序列的长度

        base case: dp[..] = 1,即每个元素自身

最大连续子序列和

        dp数组意义:截止到第i位的子序列最大序列和

        base case: dp[0]= nums[0]

斐波那契改编:

爬楼梯:每次只能迈1/2步,统计到达楼顶的不同路径

        dp数组意义:到达第n层楼的方法数

        base case: 1. 到达第0层1种方法 2. 到达第1层1种方法

62. 统计从左上角到右下角地图的所有路径

        改编: 64. 从左上角到右下角地图路径和最少

目标和/背包问题:

最大非连续子序列和(打家劫舍)

        dp数组意义:截止到第i个房子目前抢到的钱数

        base case: 第0个房子没钱

最少平方数构成目标和

        先确定平方数的上限 (i^2 <= target)

        dp数组意义:截止到target i, 最少平方数构成 (把sum 给拆了)

        base case: 截止到target 0 , 用0个数

可放回的硬币凑数

        有点类似word break,可放回硬币凑数,

        dp数组意义:截止到target i, 使用的最少硬币数

        base case: 凑到target 0 ,花0个硬币

判断是否能够平分

        dp数组意义:能否达到j(价值总量)

        【i】:包括到第i个物品

        【j】:价值总量

        base case: dp[i][0] = true

股票问题:

       dp数组意义:第i天在持有/非持有股票的状态下,现在手上握着的钱

        【i】:天数

       【j】 1: 持有 0: 不持有

        股票问题细分:买卖次数,T+n次购买限制,是否含手续费

贪心:

跳跃游戏:

        1)返回能否跳过去

        2)返回最少跳跃次数

每个元素指当前位置能跳的距离

        dp数组意义:第i个位置之前,能跳的最远距离

             base case 0

why 贪心:最优解的上一步一定是最优解

        

        

        


原文地址:https://blog.csdn.net/weixin_57183661/article/details/137709670

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!