LeetCode 刷题感想之动态规划
在 LeetCode/剑指Offer 上刷了500题左右了,应该写一篇文章总结一下自己的感想。因为我自己是测试,所以从测试角度来写感受吧。
先说动态规划。
什么是动态规划?是经典算法思想之一,是自底向上的一种穷举,也就是说,如何让计算机更聪明地穷举,并通过空间换时间的方法来降低时间复杂度。
所以动态规划的核心就是状态转移方程,用数学语音来说,是计算机版本的数学归纳法。
1. 已知 F(0) = n.
2. 已知 F(x) = m 成立。
证明 F(x+1) = t 成立。
所以在动态规划中,最重要明确的点是,确定数组dp的定义是什么(划重点,决定了你的边界条件和状态转移方程如何定义),确定数组dp的长度,确定dp[i] 与 dp[i-1] 的关系。只要三者确定好,就可以通过一次循环得到答案。
举个例子(From leetcode https://leetcode-cn.com/problems/running-sum-of-1d-array/ )
给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。
示例 1:
输入:nums = [1,2,3,4]
输出:[1,3,6,10]
解释:动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
题解:毫无悬念,动态规划即可解决问题,dp[i] = dp[i-1] + nums[i],PS, 由于我们不需要考虑 nums 的后续处理,dp甚至不需要申请新的空间,直接使用nums即可,而且dp[0] = nums[0],只是在开发过程中需要考虑各种异常情况,答案如下:
class Solution {
public int[] runningSum(int[] nums) {
if(nums == null || nums.length == 0) return null;
if(nums.length == 1) return nums;
for(int i = 1;i < nums.length;i++){
nums[i] = nums[i-1] + nums[i];
}
return nums;
}
}
11/30/2021 补充:
学习到了区间DP,在这里补充一下:
在小区间得到最优解,再利用小区间的最优解合并,得到大区间的最优解。
伪代码:
for(int i = 0;i <= n;i++){
dp[i][j] = 初始值;
} for(int len = 2;len<=n;len++) //区间长度
for(int i = 1;i <= n;i++){
int j = i+len-1;
if(j > n) break;
for(int k = i;k<j;k++){
dp[i][j] = Math.max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
}
}
PPS, Leetcode上有大神总结得很好,参考 https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns#Minimum-(Maximum)-Path-to-Reach-a-Target
最新文章
- css样式之background详解
- [转载]Grunt插件之LiveReload 实现页面自动刷新,所见即所得编辑
- Python中的list和tuple
- 转:Xms Xmx PermSize MaxPermSize 区别
- Emoji表情符号录入MySQL数据库报错
- [转载]CAD文件版本
- c#经典俄罗斯方块 vs2012开发
- mysqldump原理1
- spring的三种注入方式
- [原创]使用GCC创建 Windows NT 下的内核DLL
- 【专章】dp基础
- python学习笔记(十一)之函数
- GitHub起步---创建第一个项目
- HMM:隐马尔科夫模型-维特比算法
- 动态性能视图v$mystat,v$sesstat,v$statname
- 实验吧—Web——WP之 what a fuck!这是什么鬼东西?
- PowerPoint’s Menu is Too Big
- tensorflow 曲线拟合
- MySQL命令:创建数据库、插入数据
- Linux基础命令---zcat