《LeetCode 746 使用最小花费爬楼梯 || LeetCode 91 解码方法》

一、题目二、做题思路2.1 状态表示核心基础本题要求计算到达每一级台阶所需的最小花费。我们定义dp[i]表示到达第i级台阶即下标为i的位置时的最小累计花费。注意楼梯顶部对应于下标为nn为数组长度即越过最后一个台阶。该定义以位置为结尾进行统计是后续推导的出发点。2.2 状态转移方程关键难点可以选择向上爬 1 个台阶或 2 个台阶因此到达第i级台阶的最后一步要么来自i-1支付cost[i-1]要么来自i-2支付cost[i-2]。为了花费最小我们在两者中取较小值dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])其中i ≥ 2。该方程将全局最优拆解为子问题最优是动态规划的核心。2.3 初始化边界防护题目允许从下标 0 或 1 的台阶开始意味着到达这两个位置无需支付任何费用因此dp[0] 0dp[1] 0。同时cost数组中的费用仅用于离开该台阶时支付与到达时的累计花费无关初始化必须符合这一语义。2.4 填表顺序递推方向计算dp[i]必须依赖dp[i-1]和dp[i-2]这些下标均小于i。因此必须从左到右即下标从小到大依次填充dp表保证每个状态计算时其所有前置状态均已就绪。2.5 返回值目标映射题目要求返回到达楼梯顶部的最小花费而楼梯顶部对应下标nn cost.lengthdp[n]正好表示该值。因此直接返回dp[n]。三、代码#include vector using namespace std; class Solution { public: int minCostClimbingStairs(vectorint cost) { int n cost.size(); //1.创建dp表 vectorint dp(n 1); //3. 初始化 dp[0] dp[1] 0;//可以从0和1开始爬因此不需要交钱 //2.状态转移方程 for (int i 2; i n; i) { //4.填写顺序从左往右 dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);//求上一步和上上步谁花钱最少到这 } return dp[n]; } };四、流程图五、题目六、做题思路6.1 状态表示核心基础本题要求计算给定字符串s的解码方法总数。我们定义dp[i]表示字符串前i个字符即s[0..i-1]的解码方法数。该定义以前缀长度为状态直接对应题目所求是后续推导的出发点。6.2 状态转移方程关键难点解码第i个字符位置i-1时最后一步有两种可能单独解码s[i-1]要求该字符不为0此时贡献dp[i-1]。与前一字符组合要求s[i-2]不为0且两位数字在10 ~ 26之间此时贡献dp[i-2]。因此方程可写为dp[i] dp[i-1] dp[i-2]但两项仅在对应条件满足时才累加具体为若s[i-1] ! 0则dp[i-1]有效否则此项为 0。若s[i-2] ! 0且(s[i-2]-0)*10 (s[i-1]-0) 26则dp[i-2]有效否则此项为 0。6.3 初始化边界防护为递推提供起始条件需设定dp[0] 1表示空串有 1 种解码方式基础情况。dp[1]取决于第一个字符若s[0] ! 0则dp[1] 1否则dp[1] 0。若字符串以0开头初始化已直接导致最终结果为 0符合题意。6.4 填表顺序递推方向计算dp[i]依赖dp[i-1]和dp[i-2]下标均小于i。因此必须从左到右即i从 2 到n依次填充dp表确保每个状态计算时其所有前置状态均已就绪。6.5 返回值目标映射题目要求返回整个字符串s的解码方法总数即长度为n的前缀对应dp[n]。因此直接返回dp[n]。若过程中任何位置无法解码转移方程会自动将对应项置零最终返回 0满足题目要求。七、代码class Solution { public: int numDecodings(string s) { int n s.size(); vectorint dp(n);//创建dp表 //初始化 if (s[0] ! 0) dp[0] 1; if (n 1) return dp[0];//边界 if (s[0] ! 0 s[1] ! 0) dp[1] 1; int t (s[0] - 0) * 10 s[1] - 0; if (t 10 t 26) dp[1] 1; for (int i 2; i n; i) { //状态转移方程dp[i]dp[i-1]dp[i-2] if (s[i] ! 0) dp[i] dp[i - 1]; int t (s[i - 1] - 0) * 10 s[i] - 0; if (t 10 t 26) dp[i] dp[i - 2]; } return dp[n - 1]; } };八、流程图九、优化代码class Solution { public: int numDecodings(string s) { int n s.size(); // 1. 创建dp表 // dp[i] 表示字符串 s 的前 i 个字符即 s[0..i-1]的解码方法总数 vectorint dp(n 1, 0); // 2. 初始化 // dp[0] 1空串可以视为一种解码方式作为后续累加的基础。 // 为什么给1当处理两位数字时若 s[1] 和 s[0] 构成合法两位数 // 则 dp[2] 需要加上 dp[0]此时 dp[0]1 代表“两位数字作为一个整体”这一种情况。 dp[0] 1; // 处理第一个字符索引0若不为 0则单独解码成一种方案 if (s[0] ! 0) dp[1] 1; // 如果字符串只有一个字符直接返回结果避免后续越界 if (n 1) return dp[1]; // 3. 填表顺序从左到右i 从 2 到 n for (int i 2; i n; i) { // 情况一当前字符 s[i-1] 单独解码必须不为 0 if (s[i - 1] ! 0) dp[i] dp[i - 1]; // 情况二当前字符与前一个字符 s[i-2] 组成两位数 int twoDigit (s[i - 2] - 0) * 10 (s[i - 1] - 0); // 合法范围10 ~ 26注意 01 等前导零不合法所以 t 10 已排除 if (twoDigit 10 twoDigit 26) dp[i] dp[i - 2]; } // 4. 返回值dp[n] 即为整个字符串的解码方法数 return dp[n]; } };