面试题16.11.跳水板----leetcode

本题可以有多种解法：本文采用动态规划的方法来处理。

状态方程：

首先本题的状态方程可以写为：dp[i]=dp[i-1]+longer-shorter;

边界条件：

其次，本题的边界条件有两个：即当k=0时和shorter等于longer时。当k=0时，返回的结果为空，当shorter=longer时，返回结果为k*shorte或者k*longer。

具体程序如下。

 1 int* divingBoard(int shorter, int longer, int k, int* returnSize){
 2     int* dp=(int *)calloc((k+2),sizeof(int));
 3     *returnSize=0;
 4     int i;
 5     dp[0]=k*shorter;
 6     if(k==0)
 7     {
 8          return dp;
 9     }
10     else if(shorter==longer)
11     {
12         *returnSize+=1;               //记录数组的长度。
13         return dp;
14     }
15     else{
16         for(i=1;i<=k+1;i++)
17         {
18            dp[i]=dp[i-1]+longer-shorter;
19            *returnSize+=1;
20         } 
21     }
22     return dp;
23 }