[Leetcode][程序员面试金典][面试题16.11][JAVA][跳水板][数学][动态规划]

谁借莪１个温暖的怀抱￠ 2023-02-24 03:49 18阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

**边界问题**

1.  k=0 ，不能产生跳水板，返回空数组
2.  shorter 等于longer，只有一种跳水板，返回longer*k  
    **思路**  
    一般情况，k块木板，k种可能  
    跳水板的长度是 shorter*(k-j)+longer\*j，其中 0 ≤ i < j ≤ k，且为升序排列

###### 1. 数学 ######

**时间复杂度：O(N^2) 空间复杂度：O(1)**

public int[] divingBoard(int shorter, int longer, int k) { 
            if(k==0){ 
                return new int[]{ };
            }
            if(shorter==longer){ 
                return new int[1]{ shorter*k};
            }
            int[] ans = new int[k+1];
            for(int i = 0 ;i<=k;i++){ 
                ans[i] = (k-i) *shorter + i*longer;
            }
            return ans;
        }

###### 2. 动态规划 ######

动态规划流程  
第 1 步：设计状态  
lengths\[i\] 为第 i 条跳水板的长度  
第 2 步：状态转移方程  
int distance = longer - shorter;  
lengths\[i\] = lengths\[i-1\] + distance;  
第 3 步：考虑初始化  
lengths\[0\] = shorter \* k;  
第 4 步：考虑输出  
return lengths;

**时间复杂度：O(N) 空间复杂度：O(1)**

public int[] divingBoard(int shorter, int longer, int k) { 
            if (k == 0) { 
                return new int[0];
            }
            if (shorter == longer) { 
                return new int[]{ shorter * k};
            }
            int distance = longer - shorter;
            int[] lengths = new int[k + 1];
            lengths[0] = shorter * k;
            for(int i = 1; i <= k; i++) { 
                lengths[i] = lengths[i-1] + distance;
            }
            return lengths;
        }

#### 【总结】 ####

###### 1.数组的使用分声明和初始化两部分，两者可同时进行，也可分开进行int\[\] array; 声明 ######

**int\[\] array = new int\{element1,element2,element3…\}; 初始化方式1**

**int\[\] array = new int\[length\]; 初始化方式2**

数组的初始化方式分为两种：

一.静态初始化：初始化时由程序员显式指定每个数组元素的初始值；

**int\[\] arrayName = new int\[\]\{element1,element2,element3…\}**

二.动态初始化：初始化时由程序员指定数组的长度，由系统初始化每个数组元素的默认值。

**int\[\] arrayName = new int\[length\];**

注意：不要同时使用静态初始化和动态初始化，也就是说，不要在进行数组初始化时，既指定数组的长度，也为每个数组元素分配初始值。

###### 2.能用简单数学推导的就用数学 本题的动态规划也是基于数学推导 ######

###### 3.动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/317613a417c04ff493dee878cf5016b5.png