算法系列：动态规划
source link: https://muyuuuu.github.io/2022/05/16/dp-series/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
算法系列：动态规划
2022-05-162022-05-20
3
977
1 分钟
动态规划作为算法中较难的部分，还是下定决心慢慢整理。人生建议：遇到太难的动态规划，建议直接放弃。动态规划解题也有技巧，一般而言题目的问题都是：移动最少的次数到达终点。此时我们只需要：
- 设置 dp 数组，数组大小一般和输入相同，但细节需要微操。dp[i] 的含义是，到达 i 的最少次数
- 对 dp 数组进行初始化，即开始动态规划时，起始所需的次数，一般为 0，不过也有特殊情况
- dp 的转移，如何从上一状态计算当前状态
掌握这三点，一般难度的动态规划是可以做出来的。
一维状态转移
45. 跳跃游戏 II
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
一维的状态转移是较为简单的动态规划。直接动态规划三步走，我们设 dp[i] 表示到达数组第 i 个位置需要的最少次数。第 i 个位置最小次数这个状态 dp[i]，有两种方式得到，要么本身最小，要么由上一个状态 +1 的来，即：dp[i] = min(dp[i], dp[i-1] +1)。
因此，我们的初始值要为 INT_MAX，因为如果用 0 初始化，dp[i] 始终为 0。我们写出程序：
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int i = 0; i < nums.size(); i++) {
// 从 i 开始，能跳到的位置
for (int j = 1; j <= nums[i]; j++) {
// 这些位置的状态
if (i + j < n) {
dp[i + j] = min(dp[i + j], dp[i] + 1);
}
}
}
return dp[n-1];
}
};
通过这一题，顺便补充一点：动态规划中，O(n2) 时间复杂度的程序比较常见，不必担心超时。
欢迎订阅我的文章
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK