JavaScript|LeetCode|动态规划|413.等差数列划分

最新推荐文章于 2024-12-18 13:41:19 发布

J_learner

最新推荐文章于 2024-12-18 13:41:19 发布

阅读量241

点赞数

分类专栏： LeetCode 文章标签：算法 leetcode

本文链接：https://blog.csdn.net/J_learner/article/details/105136459

版权

LeetCode 专栏收录该内容

43 篇文章

订阅专栏

本文探讨使用JavaScript解决LeetCode中关于等差数列划分的动态规划算法。通过分析以数组中特定元素结尾的等差子序列，建立动态规划模型，并优化算法，最终求得所有等差数列的个数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

法1：动态规划
看了题解
想法：
例如数组：A = [1,2,3,4]

等差数列至少有3个元素，故考虑以A[2]、A[3]结尾的等差数列。

以A[2]结尾的等差数列：[1,2,3] (A[2] - A[1] == A[1] - A[0])
以A[3]结尾的等差数列：
- [2,3,4] (A[3] - A[2] == A[2] - A[1])
- 因为A[3]与A[2]、A[1]成等差数列，又A[2]与A[1]、A[0]成等差数列，故A[3]与A[2]、A[1]、A[0]成等差数列。可以发现：若A[3]与A[2]、A[1]成等差数列，则以A[2]结尾的等差数列加上A[3]还是等差数列；故以A[3]结尾的等差数列数 = 以A[2]结尾的等差数列数 + 1 （此处加上的 1 为：A[3]与A[2]、A[1]，因为：1. 以A[2]结尾的等差数列不包括[A[1], A[2]]；2. 只有A[3]与A[2]、A[1]成等差数列，以A[3]结尾的等差数列数才等于（以A[2]结尾的等差数列数 + 1），否则为0

用dp[i]保存以A[i]结尾的等差数列个数，最后的结果为dp所有元素之和

/** 
* @param {number[]} A 
* @return {number} 
*/
var numberOfArithmeticSlices = function(A) {    
    var i = 0, dp = [], sum = 0;    
    dp[0] = dp[1] = 0;    
    for(i = 2; i < A.length; i++) { // 等差数列至少是3个数        
        if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {            
            dp[i] = dp[i - 1] + 1;        
        }        
        else {            
            dp[i] = 0;        
        }    
    }    
    for(i = 0; i < dp.length; i++) {        
        sum += dp[i];    
    }    
    return sum;
};

优化
想法：

发现dp[i]的值只与dp[i - 1]有关，只需两个变量保存中间值，sum在dp[i]生成时就加上

/** 
* @param {number[]} A 
* @return {number} 
*/
var numberOfArithmeticSlices = function(A) {    
    var i = 0, pre = 0, cur = 0, sum = 0;
    // cur保存以当前元素结尾的等差数列数
    // pre保存以当前元素的前一个元素结尾的等差数列数	    
    for(i = 2; i < A.length; i++) { // 等差数列至少是3个数        
        if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {            
            cur = pre + 1;        
        }        
        else {            
            cur = 0;        
        }        
        sum += cur;        
        pre = cur;    
    }    
    return sum;
};